Математическая логика. Алгебра логики

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

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

Функцией алгебры логики (или логической функцией) от n-переменных, называется n-арная операция на В.

Логическая функция f (x_1,…x_n) – это функция принимающая значения 0,1. Множество всех логических функций обозначается Р₂, множество всех логических функций от n-переменных обозначается Р₂(n). Всякая логическая функция может быть задана таблицей, в левой части которой перечислены все наборы переменных, а в правой части – значения функции на этих наборах.

Переменная х_i в функции f(x_1,…x_i, x_i, x_i+1,…,x_n) называется несущественной (или фиктивной), если f(x_1,…x_i, 0, x_i+1,…,x_n) = f(x_1,…x_i,1,x_i+1,…,x_n) при любых значениях остальных переменных, т. е. если изменение значения x_i в любом наборе значений x_1,…x_i не меняет значение функции. Говорят, что функция g получена из функции f удалением фиктивной переменной и наоборот, причем эти функции считаются равными.

Пример: f(x₁ x₂ x₃ x₄) = g(x₁,x₂) означает, что при любых значениях x₁ и x₂ f=g незавасимо от значения x₃. Удаляют фиктивные переменные поскольку они не влияют на значение функции и являются с этой точки зрения лишними.

Рассмотрим примеры логических функций:

1) Одна переменная Х имеет 4 логических функции, которые приведены в таблице 1.

Таб.1.

Х	F0	F1	F2	F3

Функции F₀ и F₃ – константы 0 и 1 соответственно;

Функция F₁ (х) = х, т. е. функция F₁ повторяет х;

Функция F₂ (х) является отрицанием х (логическая операция НЕ) и обозначается .

Все перечисленные функции являются унарными (для одной переменной) функциями.

2) Две переменные имеют 16 логических функций (таблица 2).

Таб. 2

х1

х2

F0

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

Все функции в таблице 2 являются бинарными (для двух переменных).

Функции F₀ и F₁₅ – константы 0 и 1;

Функция F₁ (х_1, х₂) называется конъюнкцией х₁ и х_2, обозначается: &, ,но чаще всего значок конъюнкции опускают, аналогично знаку умножения. Она ровна единице только тогда когда х₁ и х₂ =1. В остальных случаях она ровна 0. Это функция логического «И» или функция логического умножения.

Функция F₇ (х_1, х₂) называется дизъюнкцией х₁ и х_2, обозначается +, . Она ровна 1, если хотя бы одна переменная равна 1. Это функция логического «ИЛИ» или функция логического сложения.

Функция F₆ (х_1, х₂) – сложение по модулю 2, обозначается . Она ровна 1 когда значения ее аргументов различны и ровна 0 когда значения ее аргументов ровны, поэтому эта функция называется неравнозначностью.

Функция F₉ (х_1, х₂) – эквивалентность (равнозначность), обозначается «». Она ровна 1 когда аргументы ровны и ровна 0 когда аргументы различны.

Функция F₁₃ (х_1, х₂) – импликация, обозначается . Звучит данная функция так: “если х_1, то х₂ “.

Функция F₈ (х_1, х₂) – стрелка Пирса, обозначается

Функция F₁₄ (х_1, х₂) – штрих Шеффера, обозначается х_1, х₂

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

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

Задание №4

Построить таблицу истинности для формулы:

Таб. 3

X	Y				f