Исчисление высказываний

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

 

а	b	a^b	aÚ b	a ύ b	а®b	аºb
И	И	И	И	Л	И	И
И	Л	Л	И	И	Л	Л
Л	И	Л	И	И	И	Л
Л	Л	Л	Л	Л	И	И

 

а	ā
И	Л
Л	И

 

Буквы а, b - переменные, обозначающие суждения; буква “И” обозначает истину, а “Л” - ложь.

Таблицу истинности для конъюнкции (а Ù b) можно разъяс­нить на следующем примере. Учителю дали короткую характе­ристику, состоящую из двух простых суждений: “Он является хорошим педагогом (а) и учится заочно (b)”. Она будет истинна в том и только в том случае, если суждения а и b оба истинны. Это и отражено в первой строке. Если же о ложно, или b ложно, или и а, и b ложны, то вся конъюнкция обращается в ложь, т. е. учителю была дана ложная характеристика.

Суждение “Увеличение рентабельности достигается или путем повышения производительности труда (а), или путем снижения

 

себестоимости продукции (b)” - пример нестрогой дизъюнкции. Дизъюнкция называется нестрогой, если члены дизъюнкции не исключают друг друга. Высказывание или формула с такой дизъ­юнкцией истинна в том случае, когда истинно хотя бы одно из двух суждений (первые три строки таблицы), и ложна, когда оба суждения ложны.

Строгая дизъюнкция (а ύ b ) - та, в которой члены дизъюнк­ции исключают друг друга. Ее можно разъяснить на примере:

“Я поеду на Юг на поезде (а) или полечу туда на самолете (b)”. Я не могу одновременно ехать на поезде и лететь на самолете. Строгая дизъюнкция истинна тогда, когда лишь одно из двух про­стых суждений истинно, и только одно.

Таблицу для импликации (а → b) можно разъяснить на таком примере: “Если по проводнику пропустить электрический ток (а), то проводник нагреется (b)¹. Импликация истинна всегда, кроме одного случая, когда первое суждение истинно, а второе - ложно. Действительно, не может быть, чтобы по проводнику пропусти­ли электрический ток, т. е. суждение (а) было истинным, а про­водник не нагрелся, т. е. чтобы суждение (b) было ложным.

В таблице эквиваленция (a ≡ b) характеризуется так: а ≡ b истинно в тех и только в тех случаях, когда и а, и b либо оба истинны, либо оба ложны.

Отрицание суждения а (т. е. ā) характеризуется так: если а истинно, то его отрицание ложно, и если а - ложно, то . ā - истинно.

Если в формулу входят три переменные, то таблица истинности для этой формулы, включающая все возможные комбинации истинности или ложности ее переменных, будет состоять из 2³ = 8 строк; при четырех переменных в таблице будет 2⁴ = 16 строк; при пяти переменных в таблице имеем 2⁵ = 32 строки; при n переменных 2ⁿ строк.

Алгоритм распределения значений И и Л для переменных (например, для четырех переменных а, b, с, d) таков: (см. таблицу на стр. 81);

_______________________________

¹Мы отвлекаемся здесь от различия между импликацией логики высказываний и содержательным союзом “если..., то”.

 

 

 

Имеем 2⁴ = 16 строк. В столбце для а сначала пишем 8 раз “И” и 8 раз “Л”. В столбце для b сначала пишем 4 раза “И” и 4 раза “Л”, затем повторяем и т. д.

Тождественно-истинной формулой называется форму­ла, которая при любых комбинациях значений для входя­щих в нее переменных прини­мает значение “истина”. Тож­дественно-ложная формула -та, которая (соответственно) принимает только значение “ложь”. Выполнимая формула может принимать значения как “истина”, так и “ложь”.

 

а	b	с	d
и	и	и	и
и	и	и	л
и	и	л	и
и	и	л	л
и	л	и	и
и	л	и	л
и	л	л	и
и	л	л	л
л	и	и	и
л	и	и	л
л	и	л	и
л	и	л	л
л	л	и	и
л	л	и	л
л	л	л	и
л	л	л	л

 

Приведем доказательство тождественной истинности фор­мулы:

а	b	с				b ^ c	a → (b ^ c).	(V )	(a → (b ^ c)) ^ (V )	((a → (b ^ c)) ^ (V )) →
и	и	и	л	л	л	и	и	л	л	и
и	и	л	л	л	и	л	л	и	л	и
и	л	и	л	и	л	л	л	и	л	и
и	л	л	л	и	и	л	л	и	л	и
л	и	и	и	л	л	и	и	л	л	и
л	и	л	и	л	и	л	и	и	и	и
л	л	и	и	и	л	л	и	и	и	и
л	л	л	и	и	и	л	и	и	и	и

 

 

 

Так как в последней колонке имеем одни истины, то формула является тождественно-истинной, или законом логики (или, как иногда ее называют, тавтологией).

Итак,конъюнкция(а ^ b) истинна тогда, когда оба про­стых суждения истинны.Строгая дизъюнкция (а ύ b) истин­на тогда, когда только одно простое суждение истинно.Нестро­гая дизъюнкция (а v b ) истинна тогда, когда хотя бы одно про­стое суждение истинно.Импликация (а → b) истинна во всех случаях, кроме одного: когда а - истнно, b - ложно.Эквиваленция (а b) истинна тогда, когда оба суждения истинны или оба ложны.Отрицание () истины дает ложь, и наоборот.