14. Основные понятия математической логики. Основные логические операцию. Аксиомы и законы алгебры логики.

Понятия:

• Суждение - это некоторое высказывание, которое может быть истинным или ложным.

• Утверждение - это суждение, которое требуется доказать или опровергнуть.

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

• Логика- это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений.

• Высказывание - это повествовательное предложение, о котором можно сказать, истинно оно или ложно.

Основные логические операции:

• Конъюнкция – логическое умножение.

• Дизъюнкция – логическое сложение

• Инверсия – логическое отрицание.

• Импликация – логическое следование. Из истины следует ложь равно ложь. В остальных случаях истина.

• Эквивалентность – равноценность.

Аксиомы и законы:

1. ,  закон снятия двойного отрицания.

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

15. Логические функции двух переменных. Таблица истинности логических функций.

Представленные 16 функций называются элементарными. Функции   и  являются константами соответственно 0 и 1.

 - есть конъюнкция (логическое умножение)

 альтернатива (сложение по модулю 2) 

 дизъюнкция

 функция Вебба (или-не) 

 эквивалентность (равнозначность)

 функция Шеффери (и-не) 

16. Совершенные нормальные формы логических функций.

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

• в ней нет одинаковых элементарных конъюнкций

• в каждой конъюнкции нет одинаковых пропозициональных букв

• каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФпропозициональных букв, причём в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причём единственная.

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

• в ней нет одинаковых элементарных дизъюнкций

• в каждой дизъюнкции нет одинаковых пропозициональных переменных

• каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

17. Совершенные нормальные формы логических функций двух переменных.

18. Элементы НЕ, И, ИЛИ. Функциональные схемы в элементах НЕ, И, ИЛИ.

Схема И.

Схема И реализует конъюнкцию двух или более логических значений.

Условное обозначение на структурных схемах схемы И с двумя входами представлено на рис. 1. Таблица истинности — в таблице 1.

 Рис. 1

Таблица 1

X	Y	XY
0	0	0
0	1	0
1	0	0
1	1	1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом z этой схемы и входами x и y описывается соотношением: z = xy (читается как "x и y").

Операция конъюнкции на функциональных схемах обозначается знаком “&” (читается как "амперсэнд"), являющимся сокращенной записью английского слова and.

Схема ИЛИ

Схема ИЛИ реализует дизъюнкцию двух или более логических значений.

Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица.

Условное обозначение схемы ИЛИ представлено на рис. 2. Знак “1” на схеме — от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как "x или y"). Таблица истинности — в табл. 2.

 Рис. 2

Таблица 2

X	Y	X v Y
0	0	0
0	1	1
1	0	1
1	1	1

Схема НЕ

Схема НЕ (инвертор) реализует операцию отрицания. Связь между входом x этой схемы и выходом z можно записать соотношением z = ¬ x, где ¬ x читается как "не x" или "инверсия х".

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение инвертора — на рисунке 3, а таблица истинности — в табл. 3.

 Рис. 3

Таблица 3

x	¬x
0	1
1	0