Основы логики

Основоположником математической логики является английский математик Джордж Буль (1815 – 1864). Он впервые высказал идеи логического истолкования теории множеств.

Рассмотрим 2^х элементное множество B, элементы которого 0 и 1. Однако они не являются числами в обычном смысле. Наиболее распространенная интерпретация двоичных переменных – это логические: “ДА – НЕТ” или “ИСТИННО – ЛОЖНО”. Например: в языках программирования вводится специальный тип переменной – логическая переменная, значения которой обозначаются TRUE и FALSE.

Таким образом, элементы множества B={0,1} будем рассматривать как формальные символы, а не числа.

Алгебра, образованная множеством B вместе со всеми возможными операциями на нем, называется алгеброй логики или Булевой алгеброй.

Булевой функцией f(x₁, x₂, …, x_n) называется функция, которая принимает два значения 0 или 1 в зависимости от переменных х_i, каждая из которых может также принимать только два значения 0 или 1.

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

Рассмотрим основные функции алгебры логики.

1. Логическое отрицание (инверсия) обозначается чертой над аргументом. Это функция одной переменной:

f(x) = x; 0 =1; 1=0.

2. Логическое сложение (дизъюнкция). Это функция нескольких переменных. Функция обозначается следующим образом:

f(x₁,x₂) = x₁ V x₂ V x₃…

Для двух переменных таблица истинности имеет вид:

x₁ x₂ f(x₁,x₂)

0 0 0

0 1 1

1 0 1

1 1 1

3. Логическое умножение (конъюнкция). Это функция нескольких переменных. Функция обозначается следующим образом:

f(x₁x₂) = x₁ /\ x₂ /\ х₃ …

Функция определяется следующей таблицей истинности для двух переменных.

x₁ x₂ f(x₁x₂)

0 0 0

0 1 0

1 0 0

1 1 1

4. Функция Шеффера – реализует умножение с отрицанием. Определяется для двух переменных следующей таблицей истинности. Это функция нескольких переменных:

x₁ x₂ f(x₁x₂)

0 0 1

0 1 1

1 0 1

1 1 0

Функция имеет вид:

f(x₁x₂) = x₁½x₂ = x₁ /\ x₂

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

x₁ x₂ f(x₁x₂)

0 0 1

0 1 0

1 0 0

1 1 0

Функция имеет вид: f(x₁x₂) = x₁ ¯ x₂ = x₁ Ú x₂

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

6. Сложение по mod 2. Выполняет логическую операцию XOR. Это функция нескольких переменных и определяется следующей таблицей истинности для двух переменных:

x1	x2	Y

Функция имеет вид Y =x₁ Å x₂

Всякая логическая функция “n” переменных может быть задана таблицей, в левой части которой перечислены все 2ⁿ наборов значений переменных, а в правой части – значения функции на этих наборах. Например, для 3-х переменных имеем:

x1	x2	x3	f

Наборы (строки) х на которых функция f=1 называют единичным набором, а множество единичных наборов – единичным множеством f.

Наборы х на которых f=0, называют нулевым набором f.

Составим логическую функцию из таблицы значений. Для этого возьмем конъюнкции аргументов в той строке, где функция равна единице. Причем, если аргумент равен нулю – он берется с инверсией. Если аргумент равен единице – он берется с без инверсии. Полученные конъюнкции соединяем дизъюнкцией. Для нашего примера имеем три конъюнкции (три строки таблицы, где функция равна единице). Логическая функция имеет вид:

f = (X1 /\ X2 /\ X3) \/ (X1 /\ X2 /\ X3) \/ (X1 /\ X2 /\ X3)

Инверсия обозначается чертой над аргументом. В первой конъюнкции аргументы Х1, Х2 взяты с инверсией, так как их значения во второй строке таблицы равны нулю. Во второй конъюнкции аргументы Х2, Х3 взяты с инверсией, так как их значения в пятой строке таблицы равны нулю. В третьей конъюнкции аргумент Х2 взят с инверсией, так как его значение в шестой строке таблицы равно нулю. Полученные конъюнкции объединены операциями дизъюнкции.

Дата добавления: 2013-12-13