Файл: Отчет по заданию 1 Задание 1.docx

Задание 1

Для следующих формул найти СДНФ и СКНФ, каждую двумя способами (путем равносильных преобразований и используя таблицы истинности):(Х \/ НЕ Z) => Y /\ Z1.1 Найдём СДНФ и СКНФ, используя таблицы истинности

Y	Z	Х	¬Z	Х∨¬Z	Y∧Z	Х∨¬Z→Y∧Z	ЭК	ЭД
0	0	0	1	1	0	0		Y∨Z∨X
0	0	1	1	1	0	0		Y∨Z∨¬X
0	1	0	0	0	0	1	¬Y∧Z∧¬X
0	1	1	0	1	0	0		Y∨¬Z∨¬X
1	0	0	1	1	0	0		¬Y∨Z∨X
1	0	1	1	1	0	0		¬Y∨Z∨¬X
1	1	0	0	0	1	1	Y∧Z∧¬X
1	1	1	0	1	1	1	Y∧Z∧X

СДНФ - ¬Y∧Z∧¬X \/ Y∧Z∧¬X \/ Y∧Z∧XСКНФ - (Y∨Z∨Х) ∧ (Y∨Z∨¬Х) ∧ (Y∨¬Z∨¬Х) ∧ (¬Y∨Z∨Х) ∧ (¬Y∨Z∨¬Х)1.2 Найдём СДНФ и СКНФ путем равносильных преобразований

---

ДНФ А = (Х \/ НЕ Z) => Y /\ Z = ¬X /\ Z \/ Y /\ Z = (¬X \/ Y) /\ Z = ¬X /\ Z \/ Y /\ Z СДНФ А = ¬ X /\ Z /\ (Y \/ ¬Y) \/ Y /\ Z /\ (Х \/ ¬Х) = Y/\Z/\¬X \/ ¬Y/\ Z/\¬ X \/ Y /\ Z /\ X \/\/ Y /\ Z /\ ¬X = ¬Y∧Z∧¬X \/ Y∧Z∧¬X \/ Y∧Z∧XКНФ А = (¬X \/ Y) /\ ZСКНФ А = (¬X \/ Y \/ (Z /\ ¬Z)) /\ (Z \/ (Х /\ ¬Х) \/ (Y /\ ¬Y) ) = (Y \/ Z \/ ¬X) /\/\ (Y \/ ¬Z \/ ¬X) /\ (Y \/ Z \/ X) /\ (¬Y \/ Z \/ X) /\ (Y \/ Z \/ ¬Х) /\ (¬Y \/ Z \/ ¬Х) = = (Y∨Z∨Х) ∧ (Y∨Z∨¬Х) ∧ (Y∨¬Z∨¬Х) ∧ (¬Y∨Z∨Х) ∧ (¬Y∨Z∨¬Х) Задание 2Найдите СДНФ для всякой тождественно истинной формулы,содержащей: 1) одно переменное

Х	F(x)	ЭК
0	1	¬Х
1	1	Х

СДНФ - ¬Х \/ ХЗадание 3Найдите СКНФ для всякой тождественно ложной формулы, со-держащей: 1) одно переменное

Х	F(x)	ЭД
0	0	Х
1	0	¬Х

СКНФ - Х ∧ ¬ХЗадание 4Докажите равносильность формул сравнением их совершенных нормальных форм (конъюнктивных или дизъюнктивных).НЕ (Х ∧ НЕ Y) => (HE Y => X) = X ∧ HE Y \/ Y \/ X = X ∧ (HE Y \/ 1) \/ y = X \/ YНЕ (X => Y) \/ X \/ Y = HE(HE X \/ Y) \/ X \/ Y = HE X ∧ Y \/ X \/ Y = = Y ∧ (HE X \/ 1) \/ X = Y \/ X

X	Y	X \/ Y
0	0	0
0	1	1
1	0	1
1	1	1

Y	X	Y \/ X
0	0	0
0	1	1
1	0	1
1	1	1

---

СДНФ (X \/ Y) – HE X ∧ Y \/ X ∧ HE Y \/ X ∧ YСДНФ (Y \/ X) - HE Y ∧ X \/ Y ∧ HE X \/ Y ∧ XСДНФ (X \/ Y) = СДНФ (Y \/ X)Задание 5Найдите более простой вид формул, имеющих следующие со-вершенные нормальные формыXY \/ X НЕ Y \/ HE XY = X ∧ (Y \/ HE Y) \/ HE X ∧ Y = X \/ HE X ∧ Y == (X \/ HE X) ∧ (X \/ Y) = X \/ YОтвет: X\/YЗадание 6Используя критерий тождественной истинности и тождествен-ной ложности формулы, установить будет ли данная формулатождественно истинной, тождественно ложной или выполни-мой:НЕ (X ∧ HE Y)  HE X \/ X ∧ YНЕ X \/ Y  (HE X \/ X) ∧ ( HE X \/ Y)НЕ X \/ Y  HE X \/ Y = 1 Ответ: формула тождественно истиннаОтчет по заданию 3Задание 1Доказать тождественную истинность P ∧ Q => PHE P \/ HE Q \/ P = HE Q \/ 1 = 1

---

Задание 2.

Доказать следующие правила вывода. (A и B => C) => (А и НЕ С => НЕ B)

Задание 3.

Приёмы преобразования формул. Доказать тождественную истинность.A |- A ∨ B, B |- A ∨ B Применим Modus Ponens к формуле А и применим аксиому 6A, B |- A → A ∨ BА, А → А V ВПрименим Modus PonensА V ВЗадание 4Доказать теорему дедукции на примере n =5Задание 5.Доказать правильность или неправильность рассужденийp – многоугольник правильныйq – можно вписать окружность(p => q) /\ (HE p => HE q)

p	q	HE p	HE q	p => q	HE p => HE Q	(p => q) /\( HE p => HE q )
0	0	1	1	1	1	1
0	1	1	0	1	0	0
1	0	0	1	0	1	0
1	1	0	0	1	1	1

---

Рассуждение неверно, так как из посылок p => q и НЕ р, не следует заключение НЕ q.Отчет по заданию 4Вариант 24Записать функцию f(x1, x2, x3) и минимизировать её графическим методом, методом Карно, Квайна, Мак-Класки.

Х1	Х2	Х3	F(x1,x2,x3)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

F = HE x1 /\ HE x2 /\ x3 \/ НЕ х1 /\ х2 /\ НЕ х3 \/ х1 /\ НЕ х2 /\ НЕ 3 \/ х1 /\ НЕ х2 /\ х3Графический методМетод КарноF = HE x1 /\ HE x2 /\ x3 \/ НЕ х1 /\ х2 /\ НЕ х3 \/ х1 /\ НЕ х2 /\ НЕ 3 \/ х1 /\ НЕ х2 /\ х3

		х1 /\ НЕ х2 /\ х3	х1 /\ НЕ х2 /\ НЕ 3
НЕ х1 /\ х2 /\ НЕ х3		HE x1 /\ HE x2 /\ x3

ДНФ – x1 /\ HE x2 \/ НЕ х2 /\ х3 \/ HE x1 /\ x2 /\ HE x3Метод Квайна

	Члены f(x1, x2, x3)	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	HE x1 /\ HE x2 /\ x3	НЕ х2 /\ х3 (1,5)
2.	НЕ х1 /\ х2 /\ НЕ х3	x1 /\ HE x2 (4,5)
3.	х1 /\ НЕ х2 /\ НЕ х3
4.	х1 /\ НЕ х2 /\ х3

---