Тақырып бойынша тесттер
1. формуланың рангін табыңыз
7
6
5
4
2. формуланың рангін табыңыз
8
6
7
5
3. Дұрыс құрылған формуланы көрсетіңіз:
4. Келтірілген өрнектердің қайсысы формула болады?
Барлық жауаптар дұрыс
5. формула үшін алмастыру нәтижесін жазыңыз
6. формула үшін алмастыру нәтижесін жазыңыз
Глава 3. предикаттар логикасы
3.1 Предикат ұғымы
Анықтама 1. x1, x2, …, xn – пәндік айнымалылардың символдары болсын. Пәндік айнымалылардың (x1, x2, …, xn) топтары пәндік аймақ деп аталатын жиыныны тиісті болсын. пәндік аймағында анықталған n-орынды предикат деп, -ның тұжырымдар жиынына бейнелеуін айтады.
Мысалдарды қарастырар алдын n-орынды предикаттарға квазианықтама берейік:
Анықтама. «n айнымалыға тәуелді және келесі қасиетке ие болған баяндамалы байланысты сөйлемі: айнымалылардың орнына анық мәндер қойылғанда ақиқат немесе жалған болсын».
Мысал 1. D(x1, x2) = «x1 натурал саны x2 натурал санына бөлінеді (қалдықсыз)» - N N жиынында анықталған екі орынды предикат. Түсінікті, D(4, 2)=1, D(3, 5)=0.
Мысал 2. Q(x) = «х2<-1, x R» - R нақты сандар жиынында анықталған бір орынды предикат. Q(-1)=0, Q( )=0. Q(x) – тепе-тең жалған екендігі түсінікті, яғни Q(x) 0.
Мысал 3. R(x, y, z)= «x2+ y2 z; x, y, z R» - R3 жиынында анықталған үш орынды предикат. R(1, 1, -2)=0, R(1, 1, 2)=1.
Мысал 4. S(x, y) = «sin2ху>-3; x, y R» - екі орынды тепе-тең ақиқат предикат.
Р(x1, x2, …, xn) - аймағында анықталған n-орынды предикат болсын. Онымен келесі түрде анықталған екі жиынды байланыстырамыз:
IP={( x1, x2, …, xn ) | Р(x1, x2, …, xn)=1} – Р предикаттың ақиқаттық жиыны,
LP={( x1, x2, …, xn) | Р(x1, x2, …, xn)=0} – Р предикаттың жалғандық жиыны.
Анықтама 2. Р – -да анықталған предикат болсын. Егер IP= (LP=) болса, онда Р тепе-тең ақиқат, егер LP= (IP=) болса, онда Р тепе-тең жалған предикат деп аталады.
Егер IP және LP болса, онда Р орындалатын предикат деп айтамыз.
R 3 кеңістікте 3 мысалдағы R(x, y, z) предикаттың IP және LP жиындарын көрсетейік (1 сурет).
z IP
1 сурет
у
х
3.2 Предикаттарға логикалық амалдарды қолдану
Анықтама 3. Р – -да анықталған предикат болсын. Р предикаттың терістеуі дегеніміз белгіленетін және -да келесі түрде анықталған предикат:
P және Q – -да анықталған предикаттар болсын.
P және Q предикаттардың дизъюнкциясы (конъюнкциясы, импликациясы, эквиваленциясы) дегеніміз былай белгіленетін , ( ( , , PQ), , ) және -да келесі түрде анықталатын предикат:
( )
( )
( )
Анықтама 4. Егер аймағына тиісті кез келген ( x1, x2, …, xn ) пәндік айнымалылардың топтары үшін Р( x1, x2, …, xn ) Q( x1, x2, …, xn ) болса, онда P және Q предикаттар аймағында анықталған пара-пар предикаттар деп аталады (P Q).
Теорема 1. аймағында анықталған n – орынды предикаттардың жиыны предикаттардың бульдік алгебрасық құрайды, яғни олар үшін бульдік алгебраның келесі 19 негізгі тепе-теңдіктер орынды:
0.
1.
2.
3.
4.
5.
6.
7.
8.
9.
|
10.
11.
12.
13.
14.
15.
16.
17.
18.
|
Мұнда 1 – -дағы тепе-тең ақиқат предикаттың, ал 0 – тепе-тең жалған предикаттың белгілері.
Бұл теореманың дұрыстығы айқын. Өйткені предикаттарға қолданылатын амалдар тұжырымдарға қолданылатын амалдар көмегімен енгізілген, ал тұжырымдар бульдік алгебраны құрайды.
3.3 Кванторлық амалдар
Предикаттарды тұжырымдарға түрлендіретін амалдарды қарастырайық. М жиынында анықталған Р(х) предикат берілсін. Егер “а” – М жиынының қандай да бір элементі болса, онда Р(х) предикатта х орнына а ны қою берілген предикатты Р(а) тұжырымға айналдырады. Мұндай предикатты бірлік деп атайды. Мысалы, Р(x): “х – жұп сан” – предикат, ал Р(6) – ақиқат тұжырым, Р(3) – жалған тұжырым.
Жоғарыда айтылғанды n – орынды предикаттарға жалпылау мүмкін: егер барлық хi, i= , пәндік айнымалылардың орнына олардың мәндері қойылса, онда тұжырым алынады.
Квантификация амалдарын қарастырамыз. Бұл амалдардар да предикаттарды тұжырымдарға айналдырады.
Жалпылау кванторы
Р(х) – жиынында анықталған предикат болсын. Бұл предикатқа предикат тепе-тең ақиқат болғанда ғана ақиқат болатын тұжырымын сәйкестікке қоямыз. тұжырымы былай оқылады: “Кез келген х үшін Р(х) ақиқат ”. тұжырымы Р(х) предикатқа х айнымалы бойынша жалпылау кванторын ілу көмегімен алынған деп айтады.
символын жалпылау кванторы деп атайды. Р(х) предикатқа х айнымалы бос болып, ал тұжырымға – х жалпылау кванторымен байланған болып енеді деп айтады.
Бар болу кванторы
P(x) – жиынында анықталған предикат болсын. Бұл предикатқа предикат тепе-тең жалған болғанда ғана жалған болатын тұжырымын сәйкестікке қоямыз. тұжырымы былай оқылады:“ P(x) ақиқат болатын х табылады”. символын бар болу (табылу) кванторы деп аиаймыз. тұжырымы Р(х) предикатқа х айнымалы бойынша бар болу кванторын ілу көмегімен алынған деп айтады. х айнымалы бұл квантормен байланған болады.
Кванторлық амалдарды көп орынды предикаттарға да қолдануға болады. Мысалы, жиынында екі орынды P(x,y) предикаты берілсін. Предикаттың айнымалыларына кванторларды іліп, мынадай тұжырымдарды алуға болады:
Достарыңызбен бөлісу: |
