Математическая логика. Типовые расчеты. Лоскутова Е.С - 5 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1.1. Понятие высказывания
Определение 1. Высказывание – это повествовательное предложение, о содержании которого можно сказать, истин-
но оно или ложно.
Обозначения: A, B, C, … .
На множестве всех высказываний определена функция истинности:
=λ
,0
1,
)(A
Определение 2. Значение )(Aλ называется логическим значением или значением истинности высказывания А.
1.2. Логические операции над высказываниями
Над высказываниями определяются следующие логические операции (логические связки):
1)
отрицание («не») есть операция перехода от высказывания А к высказыванию Ā (¬A), которое истинно тогда и
только тогда, когда A ложно;
2)
конъюнкция («и») есть операция перехода от высказываний А и В к составному высказыванию А∧В, которое ис-
тинно тогда и только тогда, когда A и B истинны одновременно;
3)
дизъюнкция («или») – переход к составному высказыванию A∨B, которое является истинным, если истинно хотя
бы одно из высказываний А и В;
4)
импликация («если …, то») – переход к составному высказыванию А→В, ложному, когда А истинно и В ложно, и
истинному в остальных случаях;
5)
эквиваленция («необходимо и достаточно», «тогда и только тогда») приводит к составному высказыванию А↔В,
которое истинно, если А и В одновременно истинны или одновременно ложны;
6)
альтернативная дизъюнкция: А∆В – истинно, когда ровно одно из высказываний A и B истинно, в других случаях
– ложно.
1.3. Формулы алгебры высказываний
Определение 1. Пропозиционной переменной называется переменная, вместо которой можно подставлять конкрет-
ные высказывания.
Обозначения: X, Y, Z, …
Определение 2. Формула – это всякий объект, который построен по следующим правилам.
1.
Всякая пропозиционная переменная – это формула.
2.
Если F и G – формулы, то ¬F, F∨G, F∧G, F→G, F↔G, F∆G тоже являются формулами.
3.
Других формул нет.
Замечание 1. При записи формул необходимы приоритеты (очерёдность выполнения операций). Такие приоритеты обо-
значаются скобками. При их отсутствии сначала выполняется отрицание, затем конъюнкция, дизъюнкция, потом импликация и
эквиваленция. Внешние скобки обычно опускают.
Определение 3. Формула называется тождественно истинной или тавтологией (тождественно ложной или противо-
речием), если при любом наборе значений пропозиционных переменных, входящих в нее, она обращается в истинное
(ложное) высказывание.
Определение 4. Формула называется выполнимой (опровержимой), если существует такой набор значений пропози-
ционных переменных, который обращает эту формулу в истинное (ложное) высказывание.
1.4. Таблицы истинности
Мы определили функцию истинности на пропозиционных переменных, но тем самым она определена на любой
формуле, поскольку всякая формула F на каждом наборе переменных принимает значение истины или лжи, а значит, со-
ответственно на всяком наборе λ(F) = 1 или λ(F) = 0.
Определение 1. Таблицей истинности формулы называют таблицу, связывающую логические значения пропозици-
онных переменных и логическое значение формулы.
1.5. Равносильность формул
Определение 1. Две формулы F и G называются равносильными, если на любом наборе пропозиционных перемен-
ных λ(F) = λ(G).
Обозначения: F ≡ G.
Теорема 1 (критерий равносильности). F ≡ G тогда и только тогда, когда формула F↔G является тавтологией.
Обозначим через E тождественную истину и через ∅ – тождественную ложь.
Основные равносильности алгебры высказываний:
1) коммутативность:
4)
X
E
X
≡
∧
;
E
E
X
≡
∨ ; (7)
;XYYX ∨
≡
∨
(1) 5)
∅
≡
∅
∧
X ; XX
≡
∅
∨ ; (8)
;XYYX ∧
≡
∧ (2)
6)
X
X
X
≡
∨ ;
X
X
X
≡
∧
; (9)
2) ассоциативность: 7) законы де Моргана:
;)()( ZYXZYX ∨∨≡∨∨ (3)
Y
X
Y
X
∧
≡
∨ ; (10)
если А – истина;
если
А
–
ложь.

Страницы