Свойства логических операций

Свойства логических операций

Логические операции

Простейшим и наиболее широкоприменяемым примером такойалгебраической системы являетсямножество B, состоящее всего из двухэлементов:

B = { Ложь, Истина }.

Как правило, в математическихвыражениях Ложь отождествляется слогическим нулём, а Истина — слогической единицей, а операцииотрицания (НЕ), конъюнкции (И) идизъюнкции (ИЛИ) определяются впривычном нам понимании. Легкопоказать, что на данном множестве Bможно задать четыре унарные ишестнадцать бинарных отношений, представленных в таблице справа, однако все они могут быть полученычерез суперпозицию трёх выбранныхопераций.

Опираясь на этот математическийинструментарий, логика высказыванийизучает высказывания и предикаты. Также вводятся дополнительныеоперации, такие как эквивалентность («тогда и только тогда, когда»), импликация («следовательно»), сложение по модулю два («исключающее или»), штрихШеффера , стрелка Пирса и другие.

Логика высказываний послужилаосновным математическиминструментом при созданиикомпьютеров. Она легко преобразуетсяв битовую логику: истинностьвысказывания обозначается однимбитом (0 — ЛОЖЬ, 1 — ИСТИНА); тогдаоперация приобретает смыслвычитания из единицы; — немодульного сложения; & — умножения; — равенства; — вбуквальном смысле сложения помодулю 2 (исключающее Или — XOR); — непревосходства суммы над 1 (то есть A B = (A + B) < = 1).

Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных длялогики высказываний аксиом. Это позволило рассматривать, например, логику кубитов, тройственную логику(когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено») и др. --

Свойства логических операций

1. Коммутативность: x y = y x, {&, }.

2. Идемпотентность: x x = x, {&, }.

3. Ассоциативность: (x y) z = x (y z), {&, }.

4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю двасоответственно:

· x (y z) = (x y) (x z),

· x (y z) = (x y) (x z).

5. Законы де Мо́ ргана:

· (x y) = ( x) ( y),

· (x y) = ( x) ( y).

6. Законы поглощения:

· x (x y) = x,

· x (x y) = x.

7. Другие (1):

· x ( x) = x 0 = x x = 0.

· x ( x) = x 1 = x x = x x = 1.

· x x = x x = x 1 = x 0 = x 0 = x.

· x 1 = x 0 = x 0 = x x = x x = x.

· .

8. Другие (2):

· = = .

· = = = .

· = = .

9. Другие (3) (Дополнение законов де Мо́ ргана):

· = = .

Булевы функции. Представление булевой функции логической формулой.

Геометрическое представление

B_n можно рассматривать как единичный n-мерный куб. Каждый набор из нулей и единиц длины n задает вершину этого куба. На рис. 3.1 представлены единичные кубы B_n при n=3, 4.

Рис. 3.1.

При этом существует естественное взаимно однозначное соответствие между подмножествами вершин n-мерных единичных кубов и булевыми функциями от n переменных: подмножеству соответствует его характеристическая функция

Например, верхней грани куба B³ (ее вершины выделены на рисунке) соответствует функция f: f(0, 0, 1)=f(0, 1, 1)=f(1, 0, 1)=f(1, 1, 1) =1 и f(0, 0, 0)=f(0, 1, 0)=f(1, 0, 0)=f(1, 1, 0) =0. Очевидно, что указанное соответствие действительно взаимнооднозначное: каждая булевая функция f от n переменных задает подмножество A_f={(x₁, ..., x_n)|f(x₁, ..., x_n)=1} вершин Bⁿ. Например, функция, тождественно равная 0, задает пустое множество , а функция, тождественно равная 1, задает множество всех вершин Bⁿ.

Табличное представление

Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции f(x₁, ..., x_n)имеет n+1 столбец. В первых n столбцах указываются значения аргументов x₁, ..., x_n, а в (n+1) -ом столбце значение функции на этих аргументах - f(x₁, ..., x_n).

Таблица 3.1. Табличное представление функции f(x₁, ..., x_n)
x₁	.	.	.	x_n-1	x_n	f(x₁, ..., x_n)
	.	.	.			f(0, ..., 0, 0)
	.	.	.			f(0, ..., 0, 1)
	.	.	.			f(0, ..., 1, 0)
.	.	.	.	.	.
	.	.	.			f(1, ..., 1, 1)

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

существует такое , что при , а .

Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, а последняя - 2ⁿ-1.

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

Формулы

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

Пусть - некоторое (конечное или бесконечное) множество булевых функций. Зафиксируем некоторое счетное множество переменных V={X₁, X₂, ...}. Определим по индукции множество формул над с переменными из V. Одновременно будем определять числовую характеристику формулы называемую ее глубиной, и множество ее подформул.

Определение 3.2.

1. Базис индукции. Каждая переменная и каждая константа является формулой глубины 0, т.е. dep(X_i)=dep(c)=0. Множество ее подформул состоит из нее самой.

2. Шаг индукции. Пусть и A₁, ..., A_m - формулы, и max {dep(A_i) | i = 1,..., m} = k. Тогда выражение является формулой, ее глубина равна k+1, а множество подформул включает саму формулу и все подформулы формул A₁, ..., A_m.

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

Базис индукции. Пусть . Тогда или . В первом случае задает функцию , во втором - функцию, тождественно равную константе c.

Шаг индукции. Пусть - произвольная формула глубины . Тогда , где и A₁, ..., A_m - формулы, для которых max_{1 < = i < = m}{dep(A_i)}=k. Предположим (по индукции), что этим формулам уже сопоставлены функции g₁(X₁,..., X_n), ..., g_m(X₁,..., X_n). Тогда формула задает функцию .

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

Определение 3.3.

· Базис индукции. 0, 1 и каждая переменная являются формулами глубины 0.

· Шаг индукции. Пусть и - формулы, .

Тогда выражения и являются формулами. При этом , а .

В соответствии с этим определением выражения и являются формулами. Глубина равна 3, а глубина равна 4. Выражения же , и (X₁ + X₂ + X₃) формулами не являются (почему? ).

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

Свойства логических операций

Логические операции

B = { Ложь, Истина }.

12 3 Следующая ⇒