Question

1. Найти простейшую формулу от трёх переменных, принимающую значение 0 только на следующих наборах значений переменных: F(0,0,0) = F(0,1,1) = F(1,0,1) = F(1,1,0) 2. Найти простейшую формулу от трёх переменных, принимающую значение 1 только на следующих наборах значений переменных: F(0,0,0) = F(0,1,1) = F(1,0,1) = F(1,1,0) 3. Получить простейшую формулу от четырёх переменных (в виде минимальной КНФ и минимальной ДНФ), если столбец значений этой формулы имеет вид: 1000011100100010

Answer 1

1. Для нахождения простейшей формулы от трех переменных, принимающей значение 0 только на заданных наборах, можно использовать метод Карно. Расположим значения функции в таблицу и укрупним ячейки с единичными значениями, чтобы выделить общие части наборов:

| x1 | x2 | x3 | f(x1,x2,x3) | |----|----|----|------------| | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 |

После укрупнения получаем следующую таблицу:

| x1 | x2 | x3 | f(x1,x2,x3) | |----|----|----|------------| | 0 | X | X | 0 | | X | 0 | X | 0 | | X | X | 0 | 0 |

Теперь можем составить простейшую формулу, учитывая, что когда переменная принимает значение 0, ее отрицание принимает значение 1:

f(x1,x2,x3) = (¬x1 ∧ x2 ∧ x3) ∨ (x1 ∧ ¬x2 ∧ x3) ∨ (x1 ∧ x2 ∧ ¬x3)

2. Для нахождения простейшей формулы от трех переменных, принимающей значение 1 только на заданных наборах, также используем метод Карно:

| x1 | x2 | x3 | f(x1,x2,x3) | |----|----|----|------------| | 0 | 0 | 0 | 1 | | 0 | 1 | 1 | 1 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 |

Укрупняем ячейки:

| x1 | x2 | x3 | f(x1,x2,x3) | |----|----|----|------------| | 0 | X | X | 1 | | X | 1 | X | 1 | | X | X | 0 | 1 |

Простейшая формула для данного случая:

f(x1,x2,x3) = (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ x2 ∨ ¬x3)

3. Для получения простейшей формулы от четырех переменных, анализируем столбец значений:

1000011100100010

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

f(x1,x2,x3,x4) = (x1 ∧ ¬x2 ∧ ¬x3 ∧ ¬x4) ∨ (¬x1 ∧ ¬x2 ∧ ¬x3 ∧ x4) ∨ (¬x1 ∧ ¬x2 ∧ x3 ∧ ¬x4) ∨ (¬x1 ∧ x2 ∧ ¬x3 ∧ ¬x4) ∨ (x1 ∧ ¬x2 ∧ ¬x3 ∧ x4) ∨ (x1 ∧ ¬x2 ∧ x3 ∧ ¬x4) ∨ (¬x1 ∧ x2 ∧ x3 ∧ ¬x4) ∨ (¬x1 ∧ x2 ∧ x3 ∧ x4)

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

f(x1,x2,x3,x4) = (¬x1 ∨ x2 ∨ x3 ∨ x4) ∧ (x1 ∨ ¬x2 ∨ x3 ∨ x4) ∧ (x1 ∨ ¬x2 ∨ ¬x3 ∨ x4) ∧ (x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4) ∧ (x1 ∨ ¬x2 ∨ x3 ∨ x4) ∧ (x1 ∨ x2 ∨ ¬x3 ∨ x4) ∧ (¬x1 ∨ x2 ∨ ¬x3 ∨ x4) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4)