Логика - доступно для всех

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

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

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

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

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

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

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

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

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

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

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

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

Таблица 3.1

х

φ0

φ1

φ2

φ3

0

1

0

0

0

1

1

0

1

1

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

Таблица 3.2

х1   х2

φ0

φ1

φ2

φ3

φ4

φ5

φ6

φ7

0      0

0      1

1      0

1      1

0

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

Кон-станта 0

Конъ-юнк-ция

Левая ко-имплика-ция

Переменная х1 

Правая ко-имплика-ция

Перемен-ная х2 

Сложе-ние по mod 2

Дизъ-юнк- ция

0

&

х1

   ←

х2

٧

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

х1   х2

φ8

φ9

φ10

φ11

φ12

φ13

φ14

φ15

0      0

0      1

1      0

1      1

1

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

Стрелка Пирса

Экви-валент-ность

Отрица-ние х2

Правая имплика-ция 

Отрица-ние х1

Левая имплика-ция 

Штрих Шеф-фера

Кон-станта  1

~

¬ х2

¬ х1

|

1

 

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

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

х1 & х2, х1 · х2 (часто х1  х2), х1 Λ х2;

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

 х1 ٧ х2, иногда х1 + х2 и т.п.

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

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

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

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

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

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

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