Немного логики

В своих постах я обычно не использую какие то формальные записи, а если использую – делаю это очень редко. Этот же пост (статью) хотел сделать неким объяснением одного из заданий по логике которое мне пришлось решить с целью тренировки навыка объяснения, выделения решения по простым шагам, ну а также привнесения в тгк действительно чего то более абстрактного и формального чем обычно.

Итак, задание: дана формула (p ⊕ q) → r. При помощи последовательных замен нужно, чтобы эта формула превратилась в равносильную формулу, но так, чтобы в окончательной формуле остались лишь знаки ¬ (отрицание) и ∨ (дизъюнкция).

Перед тем, как расписывать шаги, нужно понять, что такое равносильная формула.

Если формулировать своими словами, то равносильная формула – это формула, которая эквивалента другой формуле таблицей истинности.

Приведу тривиальный пример: ¬¬А ≡ А. Что это значит вообще переводя на естественный язык? это значит, что утверждение "Неверно, что неверно, что сегодня идет дождь эквивалентно утверждению "сегодня идет дождь" ". Т.е. снятие двойного отрицание. Думаю, интуитивно это понятно, но чтобы однозначно быть уверенным, что эти две формулы эквивалентны, нам надо посмотреть на таблицы истинности обоих формул и сопоставить их:

По фото видно, что у А и ¬А противоположные значения, поэтому добавляя еще одно отрицание мы возвращаем их. Это по сути также, как работают степени в математике: ¬А это по сути то же самое что -1. ¬¬А это по сути то же самое что (- 1)², тк оба равны А и 1 соответственно.

Также перед тем, как перейти к заданию, я должен обратиться к тому, какие формулы каким равносильны, чтобы не догадываться до этого самому. Для решения нашей задачи понадобятся следующие равносильности:

Теперь уже переходим непосредственно к шагам:

1) Первым делом мы переводим импликацию в дизъюнкцию. Под А скрывается (p ⊕ q), под В – r. Таким образом у нас выходит следующее:

(p ⊕ q) → r ≡ ¬(p ⊕ q) ∨ r.

2) Далее мы переводим ⊕ (исключающую дизъюнкцию) в ⇔ (эквивалентность):

¬(p ⊕ q) ∨ r ≡ (p ⇔ q) ∨ r.

3) Следующим шагом будет перевод ⇔ в ∧ (конъюнкцию):

(p ⇔ q) ∨ r ≡ ((¬p ∨ q) ∧ (¬q ∨ p)) ∨ r.

4) Заключительным этапом будем перевод ∧ в ∨:

(¬p ∨ q) ∧ (¬q ∨ p) ∨ r ≡ (¬(¬(¬p ∨ q) ∨ (¬(¬q ∨ p))) ∨ r.

4.1) Дополнительным, но вторичным этапом будет упрощение (ибо у нас слишком много отрицаний):

Во второй формуле мы будем упрощать лишь первую подформулу, тк при упрощении второй мы получим не тот оператор который нужен по условию:

(¬(¬(¬p ∨ q))) ≡ (¬(p ∧ ¬q)) ≡ (¬p ∨ q), таким образом у нас формула (¬(¬(¬p ∨ q) ∨ (¬(¬q ∨ p))) ∨ r превращается в ((¬p ∨ q) ∨ (¬(¬q ∨ p))) ∨ r.

Задание выполнено, но чтобы удостоверится, что оно выполнено корректно, стоит расписать таблицу истинности обоих формул:

Опа. У нас несостыковка. Первая формула ложна лишь в 1 случае, вторая - в двух. Следовательно они не равносильны. Вопрос: где ошибка?

Ошибка была в дополнительном этапе, когда я хотел сократить формулу. Так как самое первое отрицание относилось ко всей дизъюнкции, мы бы не могли его убрать без смены оператора, который нам по условию был не нужен. Т.е. правильным было бы такое преобразование:

(¬(¬(¬p ∨ q) ∨ (¬(¬q ∨ p))) ∨ r ≡ ((¬p ∨ q) ∧ (¬q ∨ p)) ∨ r. Но, как я сказал ранее, оператор был бы не тот, который нужен нам по условию.

Поэтому, как бы не хотелось проверять ТИ формулы под пунктом 4, нам придется это сделать (ну точнее мне):

На фото видим полное соответствие, поэтому заключаем, что формулы эквивалентны, т.е. равносильны.

Что ж. Вот она, логика. А ведь это даже не логика предикатов...

That's all