Реализация функций формулами

Эквивалентность функций

По таблицам 2 и 3 легко заметить, что некоторые функции никак не зависят от значений некоторых своих аргументов. Так, например, функции g ₁, g ₄, f ₁, f ₁₆ не зависят от значений любого из аргументов, это константы ноль и единица. Функции f ₄ и f ₁₃ не зависят от значений аргумента у, а функции f ₆ и f ₁₁ – не зависят от аргумента х. Это позволяет выразить их как функции меньшего числа аргументов путем удаления аргумента, не влияющего на значения функции. Такой аргумент называют несущественной переменной для функции.

В противовес несущественным переменным, аргументы, от значений которых существенно зависят значения функции, называются существенными переменными. Таким образом, если переменная x_i является существенной для функции f (x ₁, x ₂,…, x_n), то обязательно существует такой набор значений остальных переменных a ₁, a ₂,…, a_{i -1}, a_{i+ 1}, a_i+2,…, a_n, что значение функции при x_i =1 не равно значению функции при x_i =0, т.е. . Для несущественной переменной такого набора не существует.

Две функции f ₁ и f ₂ называются эквивалентными или равными (обозначается это традиционно f ₁ = f ₂), если одна может быть получена из другой путем удаления или введения несущественной переменной.

Процедура удаления несущественной переменной x_i на практике заключается в удалении всех строк вида: a ₁, a ₂,…, a_{i -1}, 1, a_{i+ 1},…, a_n (т.е. таких строк, где переменная x_i равна 1) и столбца x_i из таблицы истинности функции. Введение несущественной переменной – обратный процесс.

Пример: пусть функция f (x, y, z) задана следующей таблицей истинности:

Таблица 1

	x	y	z	f (x, y, z)
¨
¨
¨
¨

Из таблицы 4 видно, что значения функции не зависят от значений переменной у, поскольку на всех фиксированных наборах значений для x и z: (0,0), (0,1), (1,0) и (1,1), – значения функции при у =0 и у= 1 одинаковы. Тем самым, у – несущественная переменная, и её можно удалить. Для этого вычеркнем из таблицы 4 все помеченные строки, где у =1, и столбец у. Оставшиеся строки и столбцы таблицы будут определять функцию от двух переменных: х и z. Оформим результат в виде новой таблицы 5. Эта таблица является таблицей истинности элементарной функции. Это импликация. Итак, исходная функция эквивалентна импликации.

Таблица 2

x	z	f (x, z)

Рассмотрим теперь процедуру включения несущественной переменной. Для этого в таблицу 5 добавим новый столбец у, расположив его между столбцами х и z, и 4 новых строки: две в середине и две в конце таблицы. Скопируем значения переменных х и z, а также значения функции из двух верхних строк в добавленные ниже них, и из двух следующих строк в последние две. Заполним значения в столбце у так, чтобы в старых строках оно было равно 0, а в добавленных – 1. Получим таблицу истинности эквивалентной функции от большего числа переменных, совпадающую с таблицей 4.

Реализация функций формулами

Классическое определение формулы алгебры логики вводится по шагам:

любая пропозициональная переменная является формулой;

если А формула, то выражение или тоже формула;

если А и В – формулы, то выражения вида (А & В), (А Ú В), (А ® В), (А º В) и прочие, где между А и В стоит пропозициональная связка, отличная от отрицания, – тоже формулы;

ничто иное не является формулой.

Формулы из пункта 1 называют элементарными. Формулы А и В из пунктов 2 и 3, если они не элементарны, называют подформулами составных формул.

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

Примеры формул:

1)

2)

3)

4) выражение вида формулой не является.

Для построения полной таблицы истинности исходную формулу разделяют на подформулы и затем вычисляют значение каждой подформулы. Таким образом, если n – это число переменных в формуле, а s – число выделенных подформул, то число столбцов в полной таблице истинности исходной формулы будет равно n + s, а число строк – 2 ⁿ. При этом последний столбец этой таблицы будет представлять значения формулы.

Для примера рассмотрим построение полной таблицы истинности формулы . Разделим её на подформулы: f ₁=Ø x, f ₂= f ₁Ú y, f ₃= f ₂® z. Тем самым, таблица будет содержать 8 строк и 6 столбцов. См. таблицу 6.

Таблица 3

x	y	z	f 1	f 2	f 3

В последнем столбце таблицы 6 находятся значения исходной формулы.

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

Рассмотрим построение сокращенной таблицы истинности на примере той же формулы: . См. таблицу 7.

Таблица 4

((Ø	x	Ú	y)	®	z)
0

 

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

Из рассмотренных примеров видно также, что значениями формулы могут быть только 0 или 1. Поэтому столбец результатов можно рассматривать, как некоторую истинностную функцию, принимающую те же значения, что и формула, на соответствующих «энках». Эта функция соответствует формуле или, как говорят, реализуется формулой, про формулу в этом случае говорят, что она реализует функцию.

Пусть функция f (х ₁, х ₂,…, х_n) реализуется формулой U (х ₁, х ₂,…, х_n). Т.к. функция f может иметь несущественные переменные, то справедливо считать, что формула U реализует любую функцию, эквивалентную f. Если x_i – несущественная переменная для функции f, то функцию f можно заменить функцией g путем удаления несущественной переменной. Тогда формула U¹, полученная из формулы U отождествлением x_i с любой из оставшихся переменных, будет реализовывать функцию g.

Для подтверждения этого факта рассмотрим формулу: . Вычислим значения этой формулы. См. таблицу 8.

Таблица 5

((z	&	(x	®	y)	Ú	(Ø y	®	Ø x))
1

 

Результат находится в столбце, отмеченном номером 4. Реализуемая формулой функция приведена в таблице 9. Эта функция имеет несущественную переменную z. Удалив эту переменную, получим функцию g (x, y), см. таблицу 10.

Таблица 6

x	y	z	f (x, y, z)

Таблица 7

x	y	g (x, y)

 

Далее отождествим в исходной формуле переменную z с переменной у. При этом будет получена новая формула: . Построим таблицу истинности этой формулы. См. таблицу 11.

Таблица 8

((у	&	(x	®	y)	Ú	(Ø y	®	Ø x))
1

 

И, как видно из таблицы 11, новая формула реализует функцию g (x, y).

Если функция f ÎP₂ реализуется формулой U [ f ₁, f ₂,…, f_s ], сконструированной из функций f ₁, f ₂,…, f_s ÎP₂, то функция f называется суперпозицией функций f ₁, f ₂,…, f_s или говорят, что функция f получена с помощью операции суперпозиции из функций f ₁, f ₂,…, f_s.