Равносильные функции.

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

1. по каждой формуле строится таблица истинности;

2. полученные таблицы сравниваются по каждому набору значений пе-ременных.

Примеры. 1) Являются ли формулы ¬(x&y) ≡ (¬x) Ú (¬y) равносильными.

Решение: Построим таблицу истинности для заданных формул, используя определения логических операций. Имеем:

х	y	x&y	¬(x&y)	¬x	¬y	(¬x) Ú (¬y)
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Рассматривая столбцы 4 и 7 видим, что заданные формулы полностью совпадают по каждому набору значений переменных, из чего следует формулы равносильны.

2) Указать элементарные высказывания их составляющие, написать формулы данных высказываний и построить истинностные таблицы. Указать, какие из высказываний равносильны.

S₁: Ученик 1 неверно сделал задачу или если ученик 2 просчитал задачу правильно, то и ученик 3 сделал это без ошибок.

S₂: Если ученик 1 правильно просчитал задачу, то либо ученик 2 ошибся, либо ученик 3 сделал ее верно.

S₃: Либо ученик 1 неверно просчитал задачу, либо ученик 2 решил ее верно в том и только в том случае, если ученик 3 решил ее верно.

Очевидно, данные сложные высказывания составлены из следующих элементарных.

А: Ученик 1 правильно просчитал задачу

B: Ученик 2 правильно просчитал задачу

C: Ученик 3 правильно просчитал задачу

Используя основные логические связки, запишем формулы данных высказываний.

S₁=¬AÚ(B→C); S₂=A→(¬BÚC); S₃=¬AÚ(B«C).

Составим истинностные таблицы данных высказываний:

А	В	С	B→C	S1	¬BÚC	S2	B«C	S3
1	1	1	1	1	1	1	1	1
1	1	0	0	0	0	0	0	0
1	0	1	1	1	1	1	0	0
1	0	0	1	1	1	1	1	1
0	1	1	1	1	1	1	1	1
0	1	0	1	1	0	1	0	1
0	0	1	1	1	1	1	0	1
0	0	0	1	1	1	1	1	1

Из таблицы видно, что высказывания S₁ и S₂ равносильны.

№3 Пусть x, y, z - следующие элементарные высказывания: х - "а" - четное число, у - "b"- четное число, z - произведение "аb" - четное число.

Написать формулы и построить функции данных формул для следующих высказываний:

S₁: если "а" - четное число, а "b" нечетное то произ-ведение "а" и "b" делится на "2";

S₂: произведение чисел "а" и "b" делится на "2" в том и только в том случае, если "а" и "b" четно;

S₃: если каждое из чисел "а" и "b" нечетно, то их произведение не делится на "2";

S₄: произведение чисел "а" и "b" не делится на "2" в том и только в том случае, если "а" и "b" нечетны.

Какие из формул S₁, S₂, S₃, S₄ равносильны?

Решение:

S₁=x&¬y→z

S₂=z«xÚy

S₃=¬(x&y) →¬z

S₄=¬z«¬x&¬y

x	y	z	¬y	x&¬y	S1	xÚy	S2	¬(x&y)	¬z	S3	S4
1	1	1	0	0	1	1	1	0	0	1	1
1	1	0	0	0	1	1	0	0	1	1	0
1	0	1	1	1	1	1	1	0	0	1	1
1	0	0	1	1	0	1	0	0	1	1	0
0	1	1	0	0	1	1	1	0	0	1	1
0	1	0	0	0	1	1	0	0	1	1	0
0	0	1	1	0	1	0	0	1	0	0	0
0	0	0	1	0	1	0	1	1	1	1	1

Функция формул S₁, S₂, S₃, S₄ представлены столбцами истинности таблицы этих формул, откуда следует, что S₂ и S₄ равносильны.

Законы логической теории

Законом логической теории является формула, принимающая значение «истина» при любой допустимой в данной теории интерпретации символов в ее составе.

В логике высказываний понятие закона совпадает с понятием тождественно-истинной формулы. Наиболее часто в практике рассуждений используются следующие законы:

1) Закон тождества А → А. Если высказывание истинно, то оно истинно.

Мысль не должна изменяться в процессе рассуждения.

Утверждение «Идет дождь» (А) должно оставаться утверждением о том, что идет дождь (А), а не подменяться фразами вроде «На самом-то деле дождя нет – так, моросит немножко».

2) Закон непротиворечия ¬(А &¬А). Два противоречащих друг другу высказывания не могут быть одновременно истинными. Допустим, что мы повстречали двух спорящих людей, один из которых говорит: «Да, это правда!» (А), а другой – «Нет, не правда!» (¬А). Разве обязательно знать, о чем они спорят, чтобы понять, что один из них лжет?

3) Закон исключенного третьего А ∨ ¬А. Из двух противоречащих высказываний по крайней мере одно истинно. Любое высказывание можно либо утверждать (А), либо отрицать (¬А) – третьего не дано. Продолжая предыдущий пример, мы легко можем утверждать, что один упомянутых в нем людей точно прав.

4) Закон двойного отрицания А ≡ ¬(¬А). Двойное отрицание высказывания равнозначно его утверждению. Предположим, что к нашим спорщикам подошел третий. Первый говорит: «Да!» (А), второй – «Нет!» (¬А), а третий заявляет второму «Все-таки ты не прав!» (¬¬А). Очевидно, что первый и третий утверждают одно и то же.

5) Закон Клавия (¬А → А) →А. Если из отрицания суждения вытекает оно само, то такое суждение заведомо истинно. Рассмотрим суждение «Существуют отрицательные суждения». Его отрицание – «Не существует отрицательных суждений» (¬А) – само является отрицательным, то есть подтверждает истинность отвергаемого в нем положения (А). Следовательно, исходное суждение является заведомо истинным (А).

6) Закон Дунса Скота ¬А → (А → В). Из заведомо ложного высказывания вытекает любое высказывание. В повседневных рассуждениях мы часто используем этот закон чтобы подчеркнуть неправдоподобность, абсурдность каких-либо высказываний. Например, в высказывании «Если он миллионер (А), то я – китайский император (В)» подразумевается невозможность указанного лица оказаться миллионером (¬А).

7) Законы Де Моргана ¬(А & В) ≡¬А∨¬В. Отрицание конъюнкции равнозначно дизъюнкции двух отрицаний. ¬(А ∨ В) ≡ ¬А &¬В. Отрицание дизъюнкции равнозначно конъюнкции двух отрицаний.

Например, отрицанием высказывания «Он был на месте преступления (А) и видел преступника (В)» будет «Он не был там (¬А) или не видел преступника (¬В)», а отрицанием высказывания «Он посетил Париж (А) или Монте-Карло (В)» будет «Он не был ни в Париже (¬А), ни в Монте-Карло (¬В)».

8) Закон контрапозиции (A → В) ≡ (¬В → ¬А). Если из одного высказывания вытекает второе, то из отрицания второго вытекает отрицание первого.

Например, высказывание «Если Джонс виновен в этом преступлении (А), то и Браун виновен (В)» равнозначно высказыванию «Если Браун не виновен (¬В), то и Джонс не виновен (¬А)».

9) Закон транзитивности импликации ((A→В) & (В→С)) → (А→С). Если из одного высказывания вытекает второе, а из него – третье, то и из первого высказывания вытекает третье. Например, из суждений «Если приходит осень, опадают листья» и «Если опадают листья, в лесу становится светлее» вытекает «Если приходит осень, в лесу становится светлее».