Основные логические функции

Алгебра логики.

Понятие алгебры.

Функцию типа f: Mⁿ→M будем называть n - арной операцией на множестве М; n называется арностью операции f.

Алгеброй А называется совокупность < > множества М с заданными на нём операциями S={f₁₁, f₁₂,..., f_1k, f₂₁, f₂₂,..., f_2l,..., f_n1,..., f_nm}

A=<M,S>, где М - называется основным или несущим множеством (или просто носителем) алгебры А. Вектор арностей алгебры называется её типом, совокупность операций S - сигнатурой алгебры.

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

В этой главе особую роль будет играть двухэлементное множество В и двоичные переменные, принимающие значения из В. Его элементы часто обозначаются 0 и 1, однако они не являются числами в обычном смысле. Наиболее распространённая интерпретация переменных - логическая: 1 - истинно, 0 - ложно. В контексте, содержащем одновременно двоичные и арифметические величины и функции, эта интерпретация фиксируется явно: например, в языках программирования (Паскаль и др.) вводится специальный тип переменной - логическая переменная, значения которой обозначаются true и false.

Алгебра, образованная множеством В вместе с всеми возможными операциями на нём, называется алгеброй логики. Функцией алгебры логики (или логической функцией) от n переменных называется n - арная операция на B. Множество всех логических функций обозначается P₂, множество всех логических функций от n переменных – P₂(n). Алгебра, образованная к - элементным множеством вместе со всеми операциями на нём, называется алгеброй к - значной логики, а n - арные операции на к - элементном множестве называются к - значными логическими функциями n переменных; множество всех к - значных функций обозначается P_k. Множество всех к - значных логических функций от n переменных обозначается P_k(n).

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

В таблице истинности наборы расположены в определённом порядке - лексикографическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. Этим упорядочением будем пользоваться и в дальнейшем. При любом фиксированном упорядочении наборов логическая функция n-переменных полностью определяется вектор - столбцом значений функции, т.е. 2ⁿ. Поэтому мощность множества |P₂(n)| т.е. число различных логических функций n переменных равно числу различных двоичных векторов длины 2ⁿ, т.е. N = .

Переменная x _i в функции f (x₁, x₂,..., x_(i-1), x_i, x_(i+1),..., x_n) называется несущественной (или фиктивной), если f (x₁, x₂,..., x_(i-1), 0,, x_(i+1),..., x_n) = f (x₁, x₂,..., x_(i-1), 1, x_(i+1),..., x_n) при любых значениях остальных переменных, если изменение значения x_i в любом наборе x₁,..., x_n не меняет значения функции.

В этом случае функция f (x₁,..., x_n) по существу зависит от n-1 переменной, т.е. представляет собой функцию g (x₁, x₂,..., x_(i-1), x_(i+1),..., x_n-1) от n-1 переменной. Говорят, что функция g получена из функции f удалением фиктивной переменной x_i, а функция f получена из g введением фиктивной переменной, причём эти функции по определению считаются равными. Например, запись f (x₁, x₂, x₃)= g (x₁, x₂) означает, что при любых значения x₁ и x₂ f = g независимо от значения переменной x_3.

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

В частности, только это доказанное равенство |P₂(n)|= справедливо при условии, что P₂(n) содержит все возможные функции n переменных, в том числе и функции с фиктивными переменными.

Основные логические функции

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

Основные объекты, изучаемые в этом разделе, - формулы алгебры логики, состоящие из букв, знаков логических опе­раций и скобок. Буквы обозначают логические (двоичные) переменные, которые принимают только два значения -"ложь" и "истина". Знаки операций обозначают логические операции (логические связки). Каждая формула задает логическую функцию - функцию от логических переменных, ко­торая сама может принимать только два логических значе­ния.

Итак, пусть В = {0, 1} - бинарное множество, элемента­ми которого являются формальные символы 1 и 0, не имею­щие арифметического смысла и интерпретируемые как {"да", "нет"}, {"истинно", "ложно"} и т.д.

Алгебра логики - алгебра, образованная множеством В ={0, 1} вместе со всеми возможными операциями на нем.

Функцией алгебры логики (или логической функцией) f от п переменных f (х₁, х₂..., х_n) называется п-арная логичес­кая операция на В, т.е. f: Вⁿ —> В. Множество всех логичес­ких функций (логических операций) обозначается Р₂, мно­жество всех логических операций п переменных - Р₂ (п).

Любую логическую функцию f (х₁, х₂..., х_n) можно задать таблицей истинности, в левой части которой выписаны все возможные наборы значений ее аргументов х₁, х₂..., х_n,, а пра­вая часть представляет собой столбец значений функций, соответствующих этим наборам. Набор значений перемен­ных, на котором функция принимает значение f =1, называ­ется единичным набором функции f; множество всех еди­ничных наборов - единичным множеством функции f. Ана­логично набор значений, на котором / = 0, называется нулевым набором функции f, а множество нулевых наборов - нулевым множеством.

Число всех возможных различающихся наборов значений п переменных логической функции f (х₁, х₂..., х_n) равно 2ⁿ (рав­но числу всех возможных двоичных векторов длины п). Число всех различных функций п переменных равно числу возмож­ных расстановок нулей и единиц в столбце с 2ⁿ строками, т.е. |Р₂ (п)|= 2²ⁿ.

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

φ₀ и φ₃, - константы 0 и 1 соответственно. Значения этих функций не зависят от переменной х, в таких случаях говорят, что переменная х является несущественной (фиктивной) для этих функций;

φ₁(х) =х (повторение переменной).

 

Таблица 3.1

х	φ0	φ1	φ2	φ3

 

Множество всех логических функций двух переменных Р₂ (2) - бинарных логических операций - представлено в табл. 3.2 своими таблицами истинности; | Р₂ (2)| = 16 функций, из которых шесть имеют фиктивные переменные.

Таблица 3.2

х1 х2	φ0	φ1	φ2	φ3	φ4	φ5	φ6	φ7
0 0 0 1 1 0 1 1
	Кон-станта 0	Конъ-юнк-ция	Левая ко-имплика-ция	Переменная х1	Правая ко-имплика-ция	Перемен-ная х2	Сложе-ние по mod 2	Дизъ-юнк- ция
		&	→	х1	←	х2		٧

 

Продолжение таблицы

х1 х2	φ8	φ9	φ10	φ11	φ12	φ13	φ14	φ15
0 0 0 1 1 0 1 1
	Стрелка Пирса	Экви-валент-ность	Отрица-ние х2	Правая имплика-ция	Отрица-ние х1	Левая имплика-ция	Штрих Шеф-фера	Кон-станта 1
	↓	~	х2	←	х1	→	|

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

φ₁(х₁, х₂) - конъюнкция (логическое умножение, операция И), обозначается:

х₁ & х₂, х₁ · х₂ (часто х₁ х₂), х₁ Λ х₂;

φ₇(х₁, х₂) - дизъюнкция (логическое сложение, операция ИЛИ), обозначается:

х₁ ٧ х₂, иногда х₁ + х₂ и т.п.

Логические функции трех и более переменных обычно за­даются (наряду с таблицами истинности) также формулами бинарных операций. Например, выражение f (х₁, х₂, х₃) = (х₁ ٧ х₂) → (х₁ & х₃) означает, что функция трех переменных f задана формулой, состоящей из символов этих перемен­ных х₁, х₂, х₃, над которыми выполняются одна унарная операция отрицания и три бинарные операции: дизъюнкция (٧), импликация (→) и конъюнкция (&).

Наиболее употребляемыми являются операции:, ٧, &, →, ~, mod2, |, ↓. Значение любой логической формулы, со­держащей знаки этих операций, можно вычислить для лю­бого набора значений переменных, используя табл. 3.1 и 3.2.

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

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

Стандартный метод установления эквива­лентности двух формул:

1) по каждой формуле восстанавливается таблица истин­ности;

2) полученные таблицы сравниваются по каждому набо­ру значений переменных, (стандартный метод требует 2 • 2ⁿ вычислений).

 

123Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: