II. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

Литература: [1] гл. 1, §2, §3, §4

 

1. ВЫСКАЗЫВАНИЯИ ПРЕДИКАТЫ. __________________________________________________________________

Определение 1. Высказыванием называют любое повествовательное предложение, о котором имеет смысл говорить, истинно оно или ложно.

_____________________________________________________________________________________________

Современная математическая логика включает в себя логику высказываний и логику предикатов.

Высказывание принято обозначать прописными буквами латинского алфавита: А, В, С и т.д. Если высказывание А истинно, то записывают А – «И», если высказывание А ложно, то записывают А – «Л».

Если заданы высказывания А и В, то из них можно составить новое высказывание, используя логические связки «и», «или», «если..., то», «тогда и только тогда, когда», а также частицу «не». Такие высказывания называют составными, а входящие в них высказывания А и В – элементарными высказываниями. Логические связки (или логические операции) принято обозначать соответственно специальными символами (Ù, Ú, ®, «, –).

Составные высказывания, образованные из высказываний А и В, определяются следующими таблицами истинностей.

Состав­ное высказывание	Читается	Название высказывания	Таблица истинности
АÙ В	А и В	Конъюнкция высказываний	А	В	АÙ В
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л
аÚ в	А или В	Дизъюнкция высказываний	А	В	АÚ В
И	И	И
И	Л	И
Л	И	И
Л	Л	Л
А®В	Если А, то В	Импликация высказываний	А	В	А ® В
И	И	И
И	Л	Л
Л	И	И
Л	Л	И
А «В	А тогда и только тогда, когда В	Эквиваленция высказываний	А	В	А «В
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И
	Неверно, что А	Отрицание высказывания А	А
И	Л
Л	И

 

Два составных высказывания А и В называются равносильными, если они одновременно истинны или одновременно ложны при любых предположениях об истинности входящих в них элементарных высказываний. В этом случае пишут А = В.

Свойства составных высказываний:

 

Для конъюнкции	Названия свойства	Для дизъюнкции
А Ù В = ВÙ А	Коммутативность	АÚ В = ВÚ А
А Ù (ВÙ С) = (А Ù В) Ù С = = А Ù ВÙ С	Ассоциативность	АÚ (ВÚ С) = (АÚ В)Ú С = = АÚ ВÚ С

 

Есть свойства, связывающие эти две операции:

(АÚ В)Ù С = (АÙ С)Ú (ВÙ С) – дистрибутивность конъюнкции относительно дизъюнкции;

(АÙ В)Ú С = (АÚ С) Ù (ВÚ С) – дистрибутивность дизъюнкции относительно конъюнкции.

Для отрицания высказываний можно записать равносильности:

1. =А – любое высказывание А равносильно высказыванию

2. А Ù = Л, в этом случае говорят, что формула А и тождественно ложна.

3. А Ú = И, в этом случае говорят, что формула А или тождественно истинна. Операции конъюнкция, дизъюнкция и отрицание высказываний связаны следующими соотношениями:

.

Эти отношения называют законами де Моргана.

Операция импликации двух высказываний может быть выражена через операции отрицания и дизъюнкции:

А ® В = Ú В.

Для импликации высказываний имеет место закон контрапозиции: А ® В = ®

Все эти свойства доказываются с помощью таблиц истинности.