+5 голосов
от Эксперт (5.8 тыс. баллов) в категории Математика
Составьте таблицу истинности, СКНФ, СДНФ, полинома Жегалкина

((p^q)->(p->r))v p

11 Ответы

+2 голосов
от
 
Лучший ответ

1 ) Введённая функция: (p⊕q→(p→r))∧v∧p

Вектор функция: 0000000000010101

Таблица истинности:

p q r v p⊕q p→r p⊕q→(p→r) (p⊕q→(p→r))∧v (p⊕q→(p→r))∧v∧p
0 0 0 0 0 1 1 0 0
0 0 0 1 0 1 1 1 0
0 0 1 0 0 1 1 0 0
0 0 1 1 0 1 1 1 0
0 1 0 0 1 1 1 0 0
0 1 0 1 1 1 1 1 0
0 1 1 0 1 1 1 0 0
0 1 1 1 1 1 1 1 0
0 голосов
от

далее

Таблица истинности:

1 0 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0 0
1 0 1 0 1 1 1 0 0
1 0 1 1 1 1 1 1 1
1 1 0 0 0 0 1 0 0
1 1 0 1 0 0 1 1 1
1 1 1 0 0 1 1 0 0
1 1 1 1 0 1 1 1 1

Совершенная дизъюнктивная нормальная форма (СДНФ)

p¬qrv ∨ pq¬rv ∨ pqrv

Совершенная конъюнктивная нормальная форма (СKНФ)

(p∨q∨r∨v) ∧ (p∨q∨r∨¬v) ∧ (p∨q∨¬r∨v) ∧ (p∨q∨¬r∨¬v) ∧ (p∨¬q∨r∨v) ∧ (p∨¬q∨r∨¬v) ∧ (p∨¬q∨¬r∨v) ∧ (p∨¬q∨¬r∨¬v) ∧ (¬p∨q∨r∨v) ∧ (¬p∨q∨r∨¬v) ∧ (¬p∨q∨¬r∨v) ∧ (¬p∨¬q∨r∨v) ∧ (¬p∨¬q∨¬r∨v)

 

0 голосов
от

далее 3

Полином Жегалкина

prvpqvpqrv


Решение

Построение совершенной дизъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает истинное значение: { 1, 0, 1, 1 } { 1, 1, 0, 1 } { 1, 1, 1, 1 }
В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:
K1: { 1, 0, 1, 1 } — p¬qrv
K2: { 1, 1, 0, 1 } — pq¬rv
K3: { 1, 1, 1, 1 } — pqrv
Объединим конъюнкции с помощью операции ИЛИ и получим совершенную дизъюнктивную нормальную форму:

K1 ∨ K2 ∨ K3 = p¬qrv ∨ pq¬rv ∨ pqrv


Построение совершенной конъюнктивной нормальной формы:Найдём наборы, на которых функция принимает ложное значение: { 0, 0, 0, 0 } { 0, 0, 0, 1 } { 0, 0, 1, 0 } { 0, 0, 1, 1 } { 0, 1, 0, 0 } { 0, 1, 0, 1 } { 0, 1, 1, 0 } { 0, 1, 1, 1 } { 1, 0, 0, 0 } { 1, 0, 0, 1 } { 1, 0, 1, 0 } { 1, 1, 0, 0 } { 1, 1, 1, 0 }
В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:
D1: { 0, 0, 0, 0 } — p∨q∨r∨v
D2: { 0, 0, 0, 1 } — p∨q∨r∨¬v
D3: { 0, 0, 1, 0 } — p∨q∨¬r∨v
D4: { 0, 0, 1, 1 } — p∨q∨¬r¬v
D5: { 0, 1, 0, 0 } — p∨¬q∨r∨v
D6: { 0, 1, 0, 1 } — p∨¬q∨r∨¬v
D7: { 0, 1, 1, 0 } — p∨¬q¬r∨v
D8: { 0, 1, 1, 1 } — p∨¬q¬r¬v
D9: { 1, 0, 0, 0 } — ¬p∨q∨r∨v
D10: { 1, 0, 0, 1 } — ¬p∨q∨r∨¬v
D11: { 1, 0, 1, 0 } — ¬p∨q∨¬r∨v
D12: { 1, 1, 0, 0 } — ¬p¬q∨r∨v
D13: { 1, 1, 1, 0 } — ¬p¬q¬r∨v

0 голосов
от

Далее 4

Объединим дизъюнкции с помощью операции И и получим совершенную конъюнктивную нормальную форму:

 

D1 ∧ D2 ∧ D3 ∧ D4 ∧ D5 ∧ D6 ∧ D7 ∧ D8 ∧ D9 ∧ D10 ∧ D11 ∧ D12 ∧ D13 = (p∨q∨r∨v) ∧ (p∨q∨r∨¬v) ∧ (p∨q∨¬r∨v) ∧ (p∨q∨¬r¬v) ∧ (p∨¬q∨r∨v) ∧ (p∨¬q∨r∨¬v) ∧ (p∨¬q¬r∨v) ∧ (p∨¬q¬r¬v) ∧ (¬p∨q∨r∨v) ∧ (¬p∨q∨r∨¬v) ∧ (¬p∨q∨¬r∨v) ∧ (¬p¬q∨r∨v) ∧ (¬p¬q¬r∨v)

0 голосов
от

Далее 5

Построение полинома Жегалкина методом Паскаля:

p q r v ((p⊕q)→(p→r))∧v∧p
0 0 0 0 0 0 0 0 0  
0 0 0 1 0 ⊕ 0 0 0 0 0  
0 0 1 0 0 0 ⊕ 0 0 0 0  
0 0 1 1 0 ⊕ 0 0 ⊕ 0 0 0 0  
0 1 0 0 0 0 0 ⊕ 0 0 0  
0 голосов
от

Далее 6

0 1 0 1 0 ⊕ 0 0 0 ⊕ 0 0 0  
0 1 1 0 0 0 ⊕ 0 0 ⊕ 0 0 0  
0 1 1 1 0 ⊕ 0 0 ⊕ 0 0 ⊕ 0 0 0  
1 0 0 0 0 0 0 0 ⊕ 0 0  
1 0 0 1 0 ⊕ 0 0 0 0 ⊕ 0 0  
0 голосов
от

Далее 7

1 0 1 0 0 0 ⊕ 0 0 0 ⊕ 0 0  
1 0 1 1 1 ⊕ 0 1 ⊕ 0 1 1 ⊕ 0 1 prv
1 1 0 0 0 0 0 ⊕ 0 0 ⊕ 0 0  
1 1 0 1 1 ⊕ 0 1 1 ⊕ 0 1 ⊕ 0 1 pqv
1 1 1 0 0 0 ⊕ 0 0 ⊕ 0 0 ⊕ 0 0  
1 1 1 1 1 ⊕ 0 1 ⊕ 1 0 ⊕ 1 1 ⊕ 0 1 pqrv
0 голосов
от

Далее 8

Построение полинома Жегалкина методом треугольника:

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
1 v r rv q qv qr qrv p pv pr prv pq pqv pqr pqrv
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 голосов
от

Далее 9 продолжение полинома Жегалкина методом треугольника:

0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 1 0 0 0 1
0 0 0 0 1 1 0 0 1
0 0 0 1 0 1 0 1
0 0 1 1 1 1 1
0 1 0 0 0 0
1 1 0 0 0
0 1 0 0
1 1 0
0
0 голосов
от

Далее 10

1. Строится треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
2. Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
3. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
4. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы.
5. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.


Построение полинома Жегалкина методом неопределённых коэффициентов:

Запишем данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами:

 

f(p,q,r,v) = a0000 ⊕ a0001v ⊕ a0010r ⊕ a0100q ⊕ a1000p ⊕ a0011rv ⊕ a0101qv ⊕ a0110qr ⊕ a1001pv ⊕ a1010pr ⊕ a1100pq ⊕ a0111qrv ⊕ a1011prv ⊕ a1101pqv ⊕ a1110pqr ⊕ a1111pqrv

...