Выполнить переход от ДНФ к СДНФ: Х= АС ̅ ∨ А ̅В ∨ ВС

Question

Выполнить переход от ДНФ к СДНФ:
Х= АС ̅ ∨ А ̅В ∨ ВС

Answer

Давайте подробнее разберем задачу по переходу от дизъюнктивной нормальной формы (ДНФ) к сокращенной дизъюнктивной нормальной форме (СДНФ), которой соответствует минимальное исчерпывающее представление функции.

Исходная функция:

$$ Х = АС̅ \ \vee \ А̅В \ \vee \ ВС $$

Здесь:

$ А̅ $ — отрицание переменной А,

$ В $ — переменная В,

$ С̅ $ — отрицание переменной С.

Шаг 1. Определение таблицы истинности

Строим таблицу истинности по переменным $ А, В, С $.

А |
В |
С |
$ АС̅ $ |
$ А̅В $ |
$ ВС $ |
$ Х $ (Функция) |

0 |
0 |
0 |
0 |
0 |
0 |
0 |

0 |
0 |
1 |
0 |
0 |
0 |
0 |

0 |
1 |
0 |
0 |
0 |
0 |
0 |

0 |
1 |
1 |
0 |
1 |
1 |
1 |

1 |
0 |
0 |
1 |
0 |
0 |
1 |

1 |
0 |
1 |
1 |
0 |
0 |
1 |

1 |
1 |
0 |
0 |
0 |
0 |
0 |

1 |
1 |
1 |
0 |
0 |
1 |
1 |

Шаг 2. Выбор строк с результатом Х = 1

Наong попадает в таблицу строки 4, 5, 6, 8 (нумеруем от 1, для удобства — это строки для которых $$ Х = 1 $$).

Строка |
А |
В |
С |
Значения функций $\ АС̅ $, $\ А̅В $, $\ ВС $ |
Х |

4 |
0 |
1 |
1 |
0, 1, 1 |
1 |

5 |
1 |
0 |
0 |
1, 0, 0 |
1 |

6 |
1 |
0 |
1 |
1, 0, 0 |
1 |

8 |
1 |
1 |
1 |
0, 0, 1 |
1 |

Шаг 3. Записываем минимальные конъюнктивные клаузы (импликанты)

Для каждой строки — формируем конъюнкцию переменных, учитывая, какие они в исходной строке:

1. Строка 4 ($A=0, B=1, C=1$)
Конъюнкция: $\ A̅ \, \wedge \, B \, \wedge \, C $

2. Строка 5 ($A=1, B=0, C=0$)
Конъюнкция: $A \, \wedge \, B̅ \, \wedge \, C̅ $

3. Строка 6 ($A=1, B=0, C=1$)
Конъюнкция: $A \, \wedge \, B̅ \, \wedge \, C $

4. Строка 8 ($A=1, B=1, C=1$)
Конъюнкция: $A \, \wedge \, B \, \wedge \, C $

Шаг 4. Записываем ДНФ как дизъюнкцию всех этих конъюнкций

$$
Х = (\ A̅ B C \ ) \vee (A B̅ C̅) \vee (A B̅ C) \vee (A B C)
$$

Это — исходная ДНФ, из которой нужно получить СОДНФ (сокращенную дизъюнктивную нормальную форму).

Шаг 5. Минимизация (метод карт Карно)

Объединяем слагаемые с помощью карт Карно или логических закономерностей, чтобы найти минимальную сумму дизъюнкций.

Обратим внимание:

В последних двух выражениях есть общие части — $A \wedge B$.

В выражениях 5 и 6 есть общий компонент $A \wedge B̅$, и второй — $C̅$ для 5 и $C$ для 6.

Общий квадратик для 5 и 6 — это:

$$
A B̅ (C̅ \vee C) = A B̅ \quad (\ потому что \ C̅ \vee C = 1)
$$

Итак,

$$
A B̅
$$

Объединение с выражением 4:

$$
A B̅ \vee A̅ B C \vee A B C
$$

Рассмотрим объединение:

В выражениях $A B C$ и $A̅ B C$: обе содержат $B C$,

Объединим их: $ (A \vee A̅) B C = 1 \times B C = B C $.

Теперь выражение:

$$
A B̅ \vee B C
$$

Итоговая минимальная СДНФ

Значит, функция можно представить как:

$$
\boxed{ Х = A B̅ \vee B C }
$$

Ответ:

Минимальная СДНФ функции $Х$:

$$
\boxed{
Х = A \overline{B} \vee B C
}
$$

Если есть вопросы по логике или нужно дальнейшее объяснение, — обращайтесь!

А	В	С	\( АС̅ \)	\( А̅В \)	\( ВС \)	\( Х \) (Функция)
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	0	1	1	1
1	0	0	1	0	0	1
1	0	1	1	0	0	1
1	1	0	0	0	0	0
1	1	1	0	0	1	1