Кнф и днф онлайн калькулятор: Построение таблицы истинности онлайн | СКНФ | СДНФ | Полином Жегалкина | Таблица истинности булевой функции онлайн

Шпаргалки по ТДУ(11-15)

11)Логический базис

Лог.базис – полная система функций алгебры логики (Совокупность логических элементов И, ИЛИ, НЕ, с помощью которых можно воспроизвести и реализовать любую ФАЛ) Фун-ции Пирса и Шеффера являются логическими базисами.  – функция И-НЕ (базис Шеффера)  – функция ИЛИ-НЕ (базис Пирса) ИЛИ – НЕ, функция Пирса И – НЕ, функция Шеффера

12)Нормальные формы ФАЛ: ДСНФ и ДНФ ФАЛ удобно представить в некоторой исходной форме, которую называют нормальной. Затем, данную форму можно преобразовать, чтобы она соответствовала наиболее простой схеме.

1.ДНФ Дизъюнктивная нормальная форма (ДНФ) — представляет собой логическую сумму отдельных логических произведений аргументов взятых с инверсией или без нее (дизъюнкция элементарных конъюкций). Примером ДНФ является выражение: где f – логическая функция; X1,X2,

X3 — аргументы 2. ДСНФ

Дизъюнктивной совершенной нормальной формой (ДСНФ) называется ДНФ, содержащая в каждом из складываемых произведений все без исключения аргументы. ДСНФ представляет собой дизъюнкцию специально вводимых функций (минтермов), которые принимают значения LOG1 на тех же наборах, что и исходная функция Для представления ФАЛ в ДСНФ, необходимо выписать все наборы входных переменных, где LOG и поставить знаки отрицания над переменными, которые равны 0 Пример ДСНФ:

Последовательность представления в ДНФ: 1) На основании тождественных преобразований , ДСНФ выражают в основном базисе. 2) Применяя дистрибутивный закон конъюнкции относительно дизъюнкции, все конъюнкции приводят к элементарным 3) Для перехода от ДНФ к ДСНФ, каждый из членов логического выражения, в которых представлены не все переменные, следует добавить выражение вида

13) Нормальные формы ФАЛ: КСНФ и КНФ.

ФАЛ удобно представить в некоторой исходной форме, которую называют нормальной. Затем, данную форму можно преобразовать, чтобы она соответствовала наиболее простой схеме. 1. КНФ Конъюнктивная нормальная форма (КНФ) представляет собой логическое произведение отдельных логических сумм аргументов с инверсией или без нее. Примером КНФ является следующее выражение: где f – логическая функция; x1,x2,x3 – аргументы 2. КСНФ Конъюнктивной совершенной нормальной формой (КСНФ) называется КНФ содержащая в каждой из перемножаемых сумм все без исключения аргументы. КСНФ представляет собой конъюнкцию специально вводимых функцию-макстермов, которые равны LOG0 там же, где и исходная функция. пример КСНФ: Для представления ФАЛ в КСНФ необходимо выписать все наборы переменных, где функция равна LOG0 и поставить знаки отрицания над 1.

Последовательность представления КНФ: 1) КСНФ, выражается в основном базисе 2) Применяя дистрибутивный закон дизъюнкции приводятся к элементарным 3) Для перехода от КНФ к КСНФ каждому из членов, которые не содержат всех элементов, добавить слагаемое типа

14) Минимизация ФАЛ методом карт Карно Задачи минимизации ФАЛ – нахождение формы функции, содержащее мин. число входных элементов о операций м.у. ними. Карты Карно представляют собой визуальный метод, который дает возможность определять члены логического выражения, к которым можно применить закон склеивания Каждая клетка карты Карно соответствует минтерму и обозначается единицей для тех минтермов, которые присутствуют в исходной функции. Например, пусть требуется минимизировать логическую функцию, заданную таблицей истинности:

Карта Карно в этом случае будет иметь вид: На карте выделен контур, который не пересекает границу изменения только одной переменной и, следовательно, минимальная формула для данной функции будет иметь вид: f = x₂. Алгоритм минимизации: 1) Проставить единицы в те клетки карты Карно, которые соответствуют членам заданного выражения ДСНФ 2)Объединяем смежные клетки, содержащие единицы так, чтобы область содержала клеток, при этом, крайние клетки считаются смежными В области не должно быть 0, она не должна быть как можно больше; число областей как можно меньше; области могут пересекаться. 3)Смотрим первую область — какие переменные не меняются. Если неменяющаяся переменная не равна 0, то ставим над ней знак инверсии Пример: Для получения функции в форме КНФ, замкнутыми областями обхватываются клетки с 0 значениями. При записи членов берутся инверсные значения переменных с неизменным значением пределов областей.

15)Минимизация ФАЛ методом Квайна-Мак-Класки. Метод основывается на задании минтермов в виде условных чисел, называемых номерами. Каждому минтерму присваивают определенный индекс, под которым понимается число единиц в двоичном представлении номера минтерма. Алгоритм: 1) Разделить двоичные векторы области единиц логической функции на секции в соответствии с их индексами. Индекс двоичного вектора = число единиц, входящих в состав этого вектора. 2) Составить таблицу интервалов, используя правило склеивания. Склеивать между собой только те двоичные векторы, которые отличаются друг от друга только в одной координате (ближайшие векторы).

Склеивание происходит по этой координате. Ближайшие векторы могут находится только в соседних секциях таблицы. 3) В конце первого этапа получают все простые импликанты логической функции. 4) Полученное множество простых импликант минимизируют, т.е. выбирают минимальное количество простых импликант, которое позволяет покрыть всю область единиц логической функции. Пример: Пример: f={0,1,3,4,7,9,11,15}

X1	X2	X3	X4	f
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0

исчисление высказываний — Найдите ДНФ и КНФ выражения

спросил

9 лет, 3 месяца назад

Изменено 2 года, 4 месяца назад

Просмотрено 111 тысяч раз

$\begingroup$

Я хочу найти DNF и CNF следующего выражения

$$ x \oplus y \oplus z $$

Я пытался использовать

$$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$

но все испортилось.

Я также нарисовал это в Wolfram Alpha, и, конечно, он показал их, но не шаги, которые нужно сделать, чтобы туда добраться.

Есть идеи, как это можно сделать?

• исчисление высказываний
• булева алгебра
• конъюнктивная нормальная форма
• дизъюнктивная нормальная форма

$\endgroup$

2

$\begingroup$

Просто запишите таблицу истинности, найти которую довольно просто, и вывести свою КНФ и ДНФ.

\begin{массив}{| с | с | с | с |} \hline X&Y&Z&\\\hline Т&Т&Т&Т\\hline T&T&F&F\\hline Т&Ф&Т&Ф\\hline T&F&F&T\\hline F&T&T&F\\hline Ф&Т&Ф&Т\\hline F&F&T&T\\hline F&F&F&F\\hline \конец{массив}

Если вы хотите найти DNF, вам нужно просмотреть все строки, которые заканчиваются на $T$. Когда вы найдете эти строки, возьмите значения $x, y, $ и $z$ из каждого соответствующего столбца. Таким образом, вы получаете $$(x \клин у \клин z) \vee (x \клин \neg y \клин \neg z) \vee (\neg x \клин y \клин \neg z) \vee (\neg х \клин \neg y \клин z).$$ Точно так же можно найти CNF

$$ (\lnot x \lor \lnot y \lor z) \land (\lnot x \lor y \lor \lnot z) \land (x \lor \lnot y \lor \ lnot z) \land (x \lor y \lor z) $$

$\endgroup$

3

$\begingroup$

Ага. В такой более общей настройке вы можете интерпретировать $\oplus$ как сложение по модулю 2 . Например, если у вас есть 5 переменных $a_1, \ldots, a_4 \in \{0, 1\}$. Тогда $a_1 \oplus \cdots \oplus a_4 = (a_1 + \ldots + a_4) \mod 2$. Используя этот факт, вы можете записать свою КНФ. Фактически, этот «метод» неявно использует таблицы истинности.

Например, предположим, что мы хотим найти КНФ $a \oplus b \oplus c \oplus d$. Затем вам нужно перечислить все дизъюнкции $a, b, c, d$ с четным числом отрицаний. В CNF вы найдете $(a \vee b \vee c \vee d)$, $(\neg a \vee \neg b \vee c \vee d)$, $(\neg a \vee b \vee \neg c \vee d)$ и т. д., но не $(\neg a \vee b \vee c \vee d)$.

Обратите внимание, что в общем случае преобразование формул с помощью преобразований эквивалентности в КНФ и ДНФ является NP-трудным.

Надеюсь мысль понятна?

$\endgroup$

3

$\begingroup$

Использование SymPy:

 >>> x, y, z = символы ('x y z')
>>> Фи = Xor(x,y,z)
 

DNF равен

 >>> to_dnf(Phi,simplify=true)
Или(И(х, у, z), И(х, Не(у), Не(z)), И(у, Не(х), Не(z)), И(z, Не(х), Нет, спасибо)))
 

В $\LaTeX$,

$$\left(x \клин y \клин z\право) \vee \left(x \клин \neg y \клин \neg z\right) \vee \left(y \клин \neg x \клин \neg z\right) \vee \left(z \wedge \neg x \wedge \neg y\right)$$

CNF равен

 >>> to_cnf(Phi,simplify= истинный)
И(Или(х, у, z), Или(х, Не(у), Не(z)), Или(у, Не(х), Не(z)), Или(z, Не(х), Нет, спасибо)))
 

В $\LaTeX$,

$$\left(x \vee y \vee z\right) \wedge \left(x \vee \neg y \vee \neg z\right) \wedge \left(y \vee \neg x \vee \neg z\right) \wedge \left(z \vee \neg x \vee \neg y\right)$$

$\endgroup$

$\begingroup$

Для DNF:

1. посмотрите на каждую строку, где $p = 1$
2. закодируйте предложение из атомов $p_i$ для строки $i$ (что дает $p$ равно 1), которое имеет $a_i$, если этот атом равен 1 в таблице истинности, и $\neg a_i$, если он равен 0. Вы используя и , чтобы объединить атомы так, чтобы только этот термин был равен 1, когда вы находитесь в этой строке. Вы можете думать об этом соединении как о продукте.
3. возьмем ИЛИ всех таких предложений, соответствующих строкам, равным 1
4. , так как это предложение является дизъюнкцией (думайте об этом как о сложении), которое составляет только 1 для уникальных строк, вы получаете, что все это только 1, когда вам нужно, чтобы оно было 1.

Для CNF:

1. Посмотрите на строки, где $p=0$
2. закодируйте предложение из атомов $p_i$ для строки $i$ (что дает p равно нулю), которое имеет $a_i$, если этот атом равен 1 в таблице истинности, и $\neg a_i$, если он равен 0. Теперь соедините их. Это не та форма, которая вам действительно нужна, поэтому инвертируйте $p_i$, чтобы получить $\neg p_i$. По Деморгансу все дизъюнкции стали союзами.
3. Теперь возьмем И всех таких дизъюнктивных предложений.
4. Это правильно, потому что всякий раз, когда вы выбираете строку, построенное вами предложение возвращает 1 ЕСЛИ, вас нет в этой строке. Поскольку вы не находитесь в этой строке, все эти строки возвращают 1 одновременно, указывая на то, что вас нет ни в одной из строк, что дает ноль. Таким образом, вы получаете все, что дает 1.

---

Если вам нужна дополнительная помощь, посмотрите это видео:

$\endgroup$

исчисление высказываний — Преобразование формулы из КНФ в ДНФ

спросил 7 лет, 1 месяц назад

Изменено 1 год, 5 месяцев назад

Просмотрено 16 тысяч раз

$\begingroup$

Как преобразовать эту формулу из CNF в DNF?

1. $(¬a \vee b) ∧ (¬b ∨ c) ∧ (¬a ∨ ¬c)$
2. $(¬a ∨ b) ∧ (¬b ∨ c) ∧ ¬(a ∧ c)$ ДеМорган
3. ?

• исчисление высказываний

$\endgroup$

1

$\begingroup$

Как в КНФ, так и в ДНФ отрицания должны находиться рядом с пропозициональными переменными, как и в исходной формуле. Таким образом, использование ДеМоргана для вытеснения отрицаний — плохой выбор, так как в конце концов им все равно придется вернуться. Вместо этого используйте распределительный закон (где я использую обозначение $\приблизительно$, чтобы сказать, что две формулы эквивалентны):

$$p \клин(r\vee s) \приблизительно (p\клин r)\vee (p\клин s)$$ Если мы применим эту формулу к $(\neg a\vee b)\wedge(\neg b\vee c)$ (и учтем, что $p$ равно $(\neg a\vee b)$, $r$ равно $ \neg b$ и $s$ равно $c$) получаем $$(\neg a\vee b)\wedge(\neg b\vee c) \ приблизительно \big((\neg a\vee b)\wedge \neg b\big)\vee \big((\neg a \vee b)\клин c\big)$$ Теперь снова воспользуемся распределительным законом, но на этот раз в скобках: $$\big((\neg a\vee b)\клин \neg b\big)\vee \big((\neg a\vee b)\wedge c\big)\приблизительно \big( (\neg a \ клин \neg b) \vee (b \клин \neg b)\big) \vee \big((\neg a \клин c)\vee (b\клин c) \big)$$ который мы можем записать с меньшим количеством скобок как $$(\neg a \клин \neg b) \vee (b \клин \neg b) \vee (\neg a \клин c)\vee (b\клин c) \приблизительно (\neg a\клин \neg б)\vee (\neg a\клин c)\vee (b\клин c)$$ Теперь это дизъюнктивная нормальная форма, однако это не все ваше упражнение, это только левая часть.