logo
кр одмита

Методические указания

Всякая логическая функция n переменных может быть задана таблицей, в левой части которой перечислены все 2ⁿ наборов значений переменных (т.е. двоичных векторов длины n), а в правой части - значения функции на этих наборах. В этой таблице (таблица истинности) наборы расположены в лексикографическом порядке, который совпадает с порядком возрастания значений наборов, рассматриваемых как двоичные числа.

Характеристическое множество логической переменной функции – это множество М1 двоичных наборов, на котором функция принимает значение 1. Логическая функция может быть задана с помощью своего характеристического множества М1 или с помощью множества М0 наборов, на котором она равна 0.

В табл. 2 приведены все булевы функции fi (х1, х2) от двух аргументов. В левом столбце показаны их выражения в терминах нескольких функций, принятых за основные, а в следующих столбцах значения, принимаемые данными функциями на каждом из четырех наборов значений аргументов х1 и х2 (приведенных в верхней части таблицы).

Таблица 2

Булевы функции от двух аргументов

х1

0

0

1

1

х2

0

1

0

1

f0 = 0– константа 0

0

0

0

0

f1 = х1  х2– конъюнкция

0

0

0

1

f2– отрицание импликации

0

0

1

0

f3 = х1

0

0

1

1

f4– отрицание обратной импликации

0

1

0

0

f5 = х2

0

1

0

1

f6 = х1  х2– сложение по модулю 2

0

1

1

0

f7 = х1  х2- дизъюнкция

0

1

1

1

f8 = х1 х2– стрелка Пирса

1

0

0

0

f9 = х1  х2– эквиваленция

1

0

0

1

f10 =х2

1

0

1

0

f11 = х2  х1– обратная импликация

1

0

1

1

f12 =х1

1

1

0

0

f13 = х1  х2– импликация

1

1

0

1

f14 = х1  х2– штрих Шеффера

1

1

1

0

f15 = 1 – константа 1

1

1

1

1

Для установления порядка выполнения операций в формулах используются скобки. При отсутствии скобок порядок устанавливается согласно приоритетам операций. Первым приоритетом обладает операция отрицания, затем выполняется . Третьим приоритетом обладают операции  и , четвертым приоритетом – операции ~ и . Для упрощения написания формул иногда символ конъюнкции опускается.

Все операции алгебры логики можно выразить через булевы операции. Справедливость формул (1)-(3) можно доказать простой подстановкой значений из табл. 2:

х  у = xy x y; (1)

х ~ у =xy  x y; (2)

х  у =x  y. (3)

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Всякая конъюнкция элементарных дизъюнкция называется конъюнктивной нормальной формой (КНФ).

Любую логическую функцию, не равную тождественно единице, можно представить в ДНФ. Любую логическую функцию, не равную тождественно нулю, можно представить в КНФ.

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

Всякую, не равную тождественно нулю, логическую функцию можно представить в виде СДНФ.

Конъюнктивная нормальная форма называется совершенной (СКНФ), если все её составляющие есть конституенты нуля.

Всякую, не равную тождественно единице, логическую функцию можно представить в виде СКНФ.

Алгоритм построения СДНФ по таблице истинности функции состоит из трех шагов.

  1. В таблице истинности выбираются наборы, на которых функция принимает значение 1 (единицы).

  2. Для наборов, выбранных на первом шаге, составляются конституенты единицы, в которые переменная входит с инверсией, если в соответствующем наборе она принимает значение 0 (ноль), и без инверсии, если в соответствующем наборе она принимает значение 1 (единицы).

  3. Составляется дизъюнкция построенных на втором шаге конституент единицы.

Алгоритм построения СКНФ по таблице истинности логической функции содержит три шага.

  1. В таблице истинности функции выбираются наборы, на которых функция принимает значение 0 (нуля).

  2. Для этих наборов составляются конституенты нуля, в которые переменная входит с инверсией, если в наборе она принимает значение единицы, и без инверсии, если в наборе она принимает значение нуля.

  3. Составляется конъюнкция построенных на предыдущем шаге конституент нуля.

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

Приведение формулы к КНФ сводится к раскрытию скобок в соответствии со вторым дистрибутивным законом в булевой формуле, содержащей знаки инверсии на самих переменных, с последующим исключение тождественных единиц и объединением равных членов.

Решение.

Построим истинностную таблицу сложного высказывания, заданного формулой S = ((х  у)  (х  z))

Очевидно, истинностная таблица будет содержать строк.Построим таблицу (табл. 3).

Таблица 3

Истинностная таблица

x

y

z

х  у

х  z

((х  у)  (х  z))

S

0

0

0

1

1

0

1

1

0

0

1

1

1

1

1

1

0

1

0

0

1

0

1

0

0

1

1

0

1

1

1

0

1

0

0

1

0

1

1

1

1

0

1

1

0

0

0

0

1

1

0

0

1

1

1

0

1

1

1

0

1

0

1

0

Согласно алгоритмам построения СДНФ и СКНФ по таблице истинности получим следующие результаты

СДНФ =

СКНФ =

Пользуясь формулами (1) и (3), построим булево выражение, эквивалентное формуле ((х  у)  (х  z))y и найдем ДНФ и КНФ

((х  у)  (х  z))y = (x  y  xz x z)y = (x  y z)y =xy yz,

откуда ДНФ = xy yz, КНФ = (x  z)y .