Карта занятия №5. Тема: Основы математической логики

Карта занятия №5.

Тема: Основы математической логики

Математическая логика – наука о методах рассуждений, при которых мы отвлекаемся от содержания рассуждений, а используем только форму и значение. Понятие. Примеры: Высказывания, простое и составное. Примеры:

Задание 1. Какие предложения являются высказываниями?

Москва – столица нашей Родины. 5-9+8 5-9+8=4 Музыка Баха слишком сложна. Земля – спутник Солнца. Логические переменные: 0,1– ЛОЖЬ, ИСТИНА. Логические функции (N переменных – 2N –различных наборов переменных). Значения –: 0,1– ЛОЖЬ, ИСТИНА.

Логические функции

Инверсия	Конъюнкция	Дизъюнкция	Импликация	Эквивалентность
Л о г и ч е с к о е
отрицание	умножение	сложение	следование	равенство
В  р у с с к о м  я з ы к е
частица «не»	союз «и»	союз «или»	оборот речи «если…,то…»	оборот речи «…т. т.т,...»
О б о з н а ч е н и е
Не А;  ¬ А;  А  ; NOT A	А и В;  А ∧ В;  А & В, А and В	А или В;  А ∨ В;  А + В;  А or В	А →  В;  А ⇒ В	А ≡ В;  А ⇔ В;   А ~ В
З н а ч е н и е  в ы р а ж е н и я
Истина, когда высказывание ложно, и наоборот	Ложь, когда хотя бы одно высказывание ложно	Истина, когда хотя бы одно высказывание истинно	Ложно, когда из истинного следует ложное	Истина, когда оба высказывания  имеют одно значение

Задание 2. Построить таблицы истинности основных логических функций.

Задание 3. Определить значения, которые принимают следующие логические функции при заданных значениях переменных:

a→ b = ?, при a= 0, b=1

a│ b = ? (штрих Шеффера – антиконъюнкция), при a= 1, b=0

Задание 4. Докажите тождественную истинность формулы ¬X→ (X→Y )

Задание 5. Постройте таблицу истинности для следующей функции: a*b + ¬a*¬b

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

свойство	для логических операций	аналогия для операций с числами
коммутативность (переместительный закон)	X ∨ Y = Y ∨ X X ∧ Y = Y ∧ X	a + b = b + a ab = ba
ассоциативность (сочетательный закон)	(X ∨ Y) ∨ Z= X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z= X ∧ (Y ∧ Z)	(a + b) + c = a + (b + c) (ab)c = a(bc)
дистрибутивность (распределительный закон)	X ∧ (Y∨ Z) =(X∧Y) ∨ (X∧Z)	a(b + c) = ab + ac
закон двойного отрицания	¬¬Х=Х	-(-a) = a
закон исключения третьего	Х ∨ ¬Х = 1
законы де Моргана (общая инверсия )	¬ (X ∨ Y) = ¬Х ∧ ¬Y ¬ (X ∧ Y) = ¬Х ∨ ¬ Y
Закон непротиворечия	Х ∧ ¬Х = 0
Правила исключения констант: Для логического сложения, Для логического умножения.	Х ∨ 1 = 1, Х ∨ 0 = X Х ∧1 = Х,  Х ∧ 0 = 0
Раскрытие импликации	X→Y= ¬X∨Y
Раскрытие эквивалентности	X↔Y=(X∧Y)∨(¬X∧¬Y)

Задание 6. Для каждого из следующих высказываний 1) найдите символическую форму2) постройте таблицу истинности. Воспользуйтесь буквенными обозначениями: X – « Джо умён»,Y– «Джим глуп», Z – «Джо получит приз.

Если Джо умен, а Джим глуп, то Джо получит приз. Джо получит приз в том и только  том случае, если он умён или Джим глуп. Если Джим глуп, а Джо не удастся получить приз, то Джо не умён.

Задание 7. Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем «Бьюике». Джонс сказал, что это был черный «Крайслер». Смит утверждал, что это был «Форд», но не синий. Они договорились запутать следствие и поэтому указывали неправильно либо марку автомобиля, либо цвет. Определите цвет и марку автомобиля.

Логические основы компьютера (три базовых логических элементов называют вентилями)

дизъюнктор X ∨ Y	конъюнктор X ∧ Y	инвертор ¬ X	штрих Шеффера ¬ (X ∧ Y)	стрелка Пирса ¬ (X ∨ Y)

Задание 9. Построить логическую схему соответствующую логическому выражению AvB∧A.

Задание 10. По логической схеме получить логическое выражение