1. Поймем вначале, какие переменные у нее являются существенными, а какие - нет.

Во-первых, легко заметить, что $x1$ - существенная переменная, поскольку есть два набора

(0,0,0) и (1,0,0)

отличающиеся только в первой координате, на которых функция различна:

f (0,0,0) = 1, f(1,0,0) = 0

Далее, $x 3$ - тоже существенная переменная, поскольку есть два набора

(0,0,0) и (0,0,1)

отличающиеся только в третьей координате, на которых функция различна:

f (0,0,0) = 1, f(0,0,1) = 0

Переменная $x2$ - наоборот, несущественная. Поскольку на всех возможных наборах, отличающихся только во второй координате:

(0,0,0) и (0,1,0)

(0,0,1) и (0,1,1)

(1,0,0) и (1,1,0)

(1,0,1) и (1,1,1)

наша функция совпадает (на первых двух наборах она равна единице, а на всех остальных парах наборов она равна нулю).

Следовательно, переменная $x2$ - несущественная.

В таком случае, от переменной $x2$ можно насильно избавиться, и получить уже функцию от двух переменных $x ,x 1 3$ , которую мы не будем отличать от исходной функции $f$ .

Как избавиться от $x2$ ? Ну, просто вычеркнуть столбец $x2$ из таблицы истинности нашей функции:

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

И что же, на этом все? Нет конечно. Должна ведь получиться таблица истинности функции от двух переменных, а у нас получилась пока ерунда - функция уже от двух переменных, но таблица у неё слишком $”$ длинная $”$ .

Теперь надо склеить полностью совпадающие столбцы таблицы в один (а совпадающие столбцы обязательно будут, это, собственно, и означает, что $x2$ была фиктивной). Получим такую таблицу истинности:

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

2. Как теперь задать эту функцию формулой? Во-первых, можно просто построить её СДНФ - это вообще универсальный способ перейти от таблице истинности к формуле. Но можно поступить быстрее. Ясно, что если взять отрицание этой функции:

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

То мы получим обыкновенную дизъюнкцию $x1 ∨ x3$ . Поэтому наша исходная функция - это отрицание дизъюнкции, т.к. если $¬f(x1,x3) = x1 ∨ x3$ , то

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

(здесь мы воспользовались законом двойного отрицания).

02 Булевы функции. Таблицы истинности. Булев куб.