Найти скнф и сднф

Условие:

Найти скнф и сднф

Решение:

Это задание по математической логике. Здесь нужно найти СКНФ (Совершенную Конъюнктивную Нормальную Форму) и СДНФ (Совершенную Дизъюнктивную Нормальную Форму) выражения. Обозначения: - x => ¬y (x имплицирует не y) - ↔ (эквивалентность) - z v ¬x (z или не x) Запишем логическое выражение: \[ x \Rightarrow \neg y \Leftrightarrow z \lor \neg x \] Пока будем работать с двумя частями отдельно и создадим таблицу истинности для каждой части. ### Таблица истинности для \[x \Rightarrow \neg y\]: | x | y | ¬y | x => ¬y | |---|---|----|--------| | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 1 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 0 | ### Таблица истинности для \[z \lor ¬x\]: | x | z | ¬x | z ∨ ¬x | |---|---|----|-------| | 0 | 0 | 1 | 1 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | | 1 | 1 | 0 | 1 | ### Объединенная таблица истинности для всего выражения: | x | y | z | ¬y | x => ¬y | ¬x | z ∨ ¬x | (x => ¬y) ↔ (z ∨ ¬x) | |---|---|---|----|---------|----|-------|----------------------| | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | ### СДНФ (Соверешенная Дизъюнктивная Нормальная Форма): Смотрим на строки, где итоговое выражение истинно (1): 1. 0 0 0: \(\neg x \land \neg y \land \neg z\) 2. 0 0 1: \(\neg x \land \neg y \land z\) 3. 0 1 0: \(\neg x \land y \land \neg z\) 4. 0 1 1: \(\neg x \land y \land z\) 5. 1 1 0: \(x \land y \land \neg z\) Соединим дизъюнкциям: \[ \text{СДНФ} = (\neg x \land \neg y \land \neg z) \lor (\neg x \land \neg y \land z) \lor (\neg x \land y \land \neg z) \lor (\neg x \land y \land z) \lor (x \land y \land \neg z) \] ### СКНФ (Соверешенная Конъюнктивная Нормальная Форма): Смотрим на строки, где выражение ложное (0): 1. 1 0 0: \(x \lor \neg y \lor z\) 2. 1 0 1: \(x \lor \neg y \lor \neg z\) 3. 1 1 1: \(x \lor y \lor z\) 4. 0 0 1: \(x \lor y \lor \neg z\) Соединим конъюнкциям: \[ \text{СКНФ} = (x \lor \neg y \lor z) \land (x \lor \neg y \lor \neg z) \land (x \lor y \lor z) \land (x \lor y \lor \neg z) \]