Задачи по съждителна логика

В тази статия ще покажем няколко формули и възможните им оценки с помощта на табличния метод.

Първа задача

Ще се опитаме да разберем кога е вярна тази формула: ϕ = (p ∧ q) ∨ ¬q. Записваме в таблицата съждителните символи p и q:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

След това дописваме към таблицата първата част на формулата: (p ∧ q), отрицанието ¬q и после цялата формула:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Сега изчисляваме стойностите в третата колона, това е проста конюнкция, а също и за отрицанието – там просто заместваме обратните стойности на тези във втората колона:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Накрая изчисляваме стойностите в последната колона. Това е цялата формула. Според нашата таблица изчисляваме дизюнкцията „между третата и четвъртата колона“. Резултат:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Втора задача

Същото условие, друга формула: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Виждаме, че във формулата има съждителните символи p и q и техните отрицания. Първо си правим таблица с двата символа и техните отрицания:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

След това добавяме формулите p ∧ ¬q и ¬p ⇒ q, които вече лесно оценяваме, защото в таблицата имаме както оценките на отделните съждения, така и на техните отрицания. Таблицата изглежда така:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Накрая остава да оценим цялата формула, която е еквивалентност между двете последни колони:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Трета задача

Третата задача вече ще е малко по-сложна, ще опитаме с три съждителни символа, при което изчисляването на таблицата се усложнява. Формулата ще изглежда така: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Тъй като имаме три съждителни символа, общият брой вариации на оценките ще е равен на осем:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

Нататък ще действаме както в предишния случай, всяка колона оценяваме във всичките осем реда. Цялата таблица ще изглежда така:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Четвърта задача

Тази задача няма да зададем като обикновена формула, а като текстова задача. Трима приятели, които искат да отидат на луд купон, където манекенки с голи гърди ще раздават закуски, не се харесват съвсем и си поставят условия, при които ще отидат на купона. Казват се Мартин, Йордан и Петър. Правилата са следните:

1. Ако Мартин отиде, ще отиде и Йордан.
2. На купона ще дойде Петър или, ако там дойде Мартин, няма да дойде Йордан.
3. Петър ще дойде тогава и само тогава, когато не дойде Мартин или не дойде Йордан.

Въпросът е: могат ли всички да дойдат на купона? Ако не, кой може да отиде на купона, без да наруши никое правило?

Първо трябва да препишем предишните словесни съждения със съждителни символи и формули. Затова нека означим съждителните символи M, J и P (Мартин, Йордан, Петър) и всеки от тях ще означава съждение от вида „Мартин ще отиде на купона“. Първото правило можем да препишем така: M ⇒ J – „ако M, то J“, тоест „ако Мартин отиде на купона, то Йордан ще отиде на купона“.

Второто правило ще препишем така. Правилото започва с изречението „На купона ще дойде Петър или…“, така че очевидно ще ни трябва дизюнкция. Засега записваме това: P ∨ … Следващата част на изречението казва: „ако там дойде Мартин, няма да дойде Йордан“. Това е импликация, при което от дясната страна още трябва да използваме отрицание. „няма да дойде Йордан“ = ¬J. Цялата импликация би изглеждала така: M ⇒ ¬J. Присъединяваме я към предишната дизюнкция: P ∨ (M ⇒ ¬J).

Третото правило ще препишем така: започваме с „Петър ще дойде тогава и само тогава“. Това означава еквивалентност: P ⇔ … След това имаме „не дойде Мартин или не дойде Йордан“, което записваме така: ¬M ∨ ¬J. Съставяме всичко заедно: (P ⇔ (¬M ∨ ¬J)).

Сега вмъкваме всички формули в таблицата и изчисляваме стойностите:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

Въпросът беше могат ли и тримата да отидат на дивия купон. Отговорът намираме в първия ред. Той съответства на случая, когато всички момчета отиват – това се вижда от трите единици в първите три колони. Изпълнени ли са всички условия? Първото да (четвъртата колона), второто също (петата колона), но последното не (последната колона), там има нула. Това означава, че ако отидат и тримата, третото условие няма да е изпълнено.

Затова търсим онези редове, в които на позициите, представляващи условията (тоест последните три колони), има само единици. Единицата означава, че условието е изпълнено. Виждаме, че това се случва в два случая: когато отидат Йордан и Петър, но Мартин не, и когато отиде само Петър.

Можеш да го изчислиш и като добавиш към таблицата формулата ϕ, която ще е конюнкция на трите условия. Така тя ще изглежда: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Така изразяваме това, което искаме – да са изпълнени всички формули (всички условия). Тогава таблицата ще изглежда така:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Още няколко задачи по табличния метод

Тъй като съм написал програма, която може от дадена формула автоматично да състави цялата таблица, трябва да я използвам както подобава и затова следват още няколко решени формули:

Формула: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Таблица:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Формула: (a ∨ ¬a) ⇔ (b ∧ ¬b). Таблица:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Формула: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Таблица:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Формула: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Таблица:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Формула: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Таблица:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$