Задание функции при помощи вектора истинности

Пример 2. Рассмотрим для примера функцию трех переменных f(х, у, z), имеющую следующую таблицу истинности:

При лексикографическом порядке расположения векторов значений переменных`хⁿ они могут быть опущены и функция полностью будет задана своим вектором значений истинности f = (10110110).

Матричный способ

Заключается в том, что множество переменных`х<sup>n</sup> разбивается на две части`у^m и`z <sup>n–m</sup> таким образом, что все возможные значения истинности вектора ` у ^m откладываются по строкам матрицы, а все возможные значения истинности вектора`z <sup>n - m</sup> ― по столбцам. Значения истинности функции f на каждом наборе `a ⁿ =(a_1, ..., a_m,a_m+1,...,a_n)помещаются в клетки, образованные пересечением строки (a_1, ..., a_m)и столбца(a_m+1,...,a_n).

В рассмотренном выше Примере 2 в случае разбиения переменных (х, у, z)на подмножества (х)и (у, z)матрица принимает вид:

Существенной особенностью матричного способа задания является то, что полные наборы переменных`хⁿ, соответствующие соседним (как по вертикали, так и по горизонтали) клеткам, различаются по одной координате.

Задание с помощью полного бинарного дерева

Для описания n-местной функции f (`х <sup>n</sup>) используется свойство бинарного дерева высоты n, заключающееся в том, что каждой висячей вершине в нем взаимно однозначно соответствует некоторый набор значений вектора`хⁿ. Соответственно, этой висячей вершине можно приписать такое же значение истинности, которое имеет на данном наборе функция f. В качестве примера (рис.1.3) приведем задание с помощью бинарного дерева рассмотренной выше трехместной функции f = (10110110).

Рис.1.3

Первый ряд цифр, приписанных висячим вершинам дерева, обозначает лексикографический номер набора, второй ― сам набор, а третий ― значение функции на нем.

Задание с помощью n - мерного единичного куба В ⁿ

Поскольку вершины В ⁿ также можно взаимно однозначно отобразить на множество всех наборов`хⁿ, то n-местную функцию f(хⁿ) можно задать, приписывая ее значения истинности соответствующим вершинам куба В ⁿ. На рис.1.4 показано задание функции f =(10110110)на кубе В³. Значения истинности приписаны вершинам куба.

Рис.1.4

Определение. Алгеброй логики называют множество булевых констант и переменных вместе с введенными на них логическими связками.

Формульное задание

Функции алгебры логики могут быть заданы в виде аналитических выражений.

Определение. Пусть Х ―алфавит переменных и констант, используемых в алгебре логики, F ―множество обозначений всех элементарных функций и их обобщений при числах переменных, превышающих 2.

Формулой над Х,F (формулой алгебры логики) назовём все записи вида:

а) х, где хÎ X;

б) ØF₁, F₁&F₂,F₁ÚF₂ , F₁®F₂, F₁º F₂, F₁ÅF₂, F₁¯F₂ , F₁ïF₂, где F₁, F₂ ― формулы над Х, F;

в) h(F₁, … ,F_n ), где n > 2, F₁,…, F_n ― формулы над Х, F, h ―обозначение обобщенной пороговой функции из F .

Как следует из определения, для двухместных элементарных функций используется инфиксная форма записи, при которой функциональный символ помещают между аргументами, для отрицания и обобщенных функций используют префиксную форму записи, при которой функциональный символ ставят перед списком аргументов.

Пример 3.

1. Выражения х&Ø(у®z); |(x, y, z Ú u) являются формулами алгебры логики, поскольку удовлетворяют данному выше определению.

2. Выражение ®х &(у | z)не является формулой алгебры логики, поскольку неправильно применена операция ®.

Определение. Функцией, реализуемой формулой F, называется функция, получаемая при подстановке значений переменных в F . Обозначим ее f(F).

Пример 4. Рассмотрим формулу F = ху Å(х®z). Для того, чтобы построить таблицу истинности реализуемой функции, необходимо последовательно с учетом силы логических связок выполнить логическое умножение ху, затем импликацию (х®z), после чего сложить полученные значения истинности по модулю 2. Результат выполнения действий показан в таблице:

Формульное представление функций позволяет априори оценивать многие свойства функций. Переход от формульного задания к таблице истинности всегда может быть выполнен путем последовательных подстановок значений истинности в элементарные функции, входящие в формулу. Обратный переход неоднозначен, поскольку одна и та же функция может быть представлена различными формулами. Он требует отдельного рассмотрения.