Выполнить преобразования для упрощения алгебраического выражения.

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

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

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

Эквивалентные преобразования формул

Столбцах. Так можно проверить

закон поглощения.

Пример : F₁®F₂ = ù F₁ÚF₂ = ù (F₁&ù F₂).

F₁	F₂	1®2	ù1Ú2	ù(1&ù2)

Л	Л	И	И	И
Л	И	И	И	И
И	Л	Л	Л	Л
И	И	И	И	И

Пример:F₁«F₂ = (F₁®F₂)&(F₂®F₁) = (ù F₁ÚF₂)&(ù F₂ÚF₁) =

= ù (ù (ù F₁ÚF₂) Úù (ù F₂ÚF₁)).

F₁	F₂	F₁«F₂	F₁®F₂	F₂®F₁	4&5	ùF₁ÚF₂	ùF₂ÚF₁	7&8	ù7Úù8	ù10

Л	Л	И	И	И	И	И	И	И	Л	И
Л	И	Л	И	Л	Л	И	Л	Л	И	Л
И	Л	Л	Л	И	Л	Л	И	Л	И	Л
И	И	И	И	И	И	И	И	И	Л	И

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

Правила замены и подстановки расширяют возможности эквивалентных преобразований формул сложных высказываний.

Пример: Дано F=(F₁®F₂) ®((F₂®F₃) ®(F₁ÚF₂ ®F₃).

1) Удалить всюду логическую связку :

F= ù (ù F₁ÚF₂)Ú(ù ( ù F₂ÚF3)Ú(ù (F₁ÚF₂) ÚF₃);

2) Опустить отрицание на элементарные формулы по закону де Моргана:

F=F₁&ù F₂ÚF₂&ù F₃Úù F₁&ù F₂ÚF₃;

3) Выполнить преобразование по закону дистрибутивности:

F=( F₁Úù F₁) &ù F₂ÚF₂&ù F₃Ú F₃;

4) Удалить член ( F₁Úù F₁), так как ( F₁Úù F₁)=и:

F=ù F₂ÚF₂&ù F₃Ú F₃;

5) Выполнить преобразование по закону дистрибутивности:

F=ù F₂Ú(F₂ÚF3) &(ù F₃Ú F₃);

6) Удалить член ( F₃Úù F₃)=и:

F=ù F₂Ú(F₂ÚF3);

7) Применить закон ассоциативности:

F=(ù F₂ÚF₂)ÚF₃;

7) Приравнять “истине” значение формулы F, т.к.

8) (ù F₂ÚF₂)=и:

F=иÚF₃=и.