Файл: Diskretnaya_matematika.doc

4. Выражение A ~ В(«А эквивалентно В») означает высказывание, кото­рое истинно тогда и только тогда, когда А и В оба истинны или оба ложны.

Такое высказывание называют эквивалентностью высказыванийAи В. Символ~означает операцию эквивалентности.

В обычной речи этой операции соответствует связка: «тогда и только тогда, когда». Примером эквивалентности может служить высказывание: «ТреугольникABCравнобедренный тогда и только тогда, когда угол при вершине В равен углу при вершине С».

4. Выражение А («не А») означает высказывание, которое истинно, когда А ложно и ложно, когда А истинно.

Такое высказывание называютотрицаниемвысказыванияА. Символ над буквой обозначает операцию отрицания.

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

2.1.3. Формулы алгебры логики

Под алгеброй логикибудем понимать алгебру, образованную множествомE= {0, 1} вместе со всеми возможными операциями на этом множестве.

В отличие от обычной алгебры, порожденной бесконечным множеством действительных чисел R, алгебра логики базируется на конечном множествеE, состоящем из двух элементов:1 («истина») и0 («ложь»).

Пусть А, В, С – произвольные высказывания, которые рассмат­риваются как величины, принимающие одно из двух логических значений (1 или 0). Применяя к ним операции конъюнкции, дизъюнкции, импли­кации, эквивалентности и отрицания, можно получить новые слож­ные высказывания, например:

((АВ)С) ~ АВ. (1)

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

Наряду с высказываниями, принимающими определенные постоянные значения (1 или 0) и называемыми постоянными высказываниями, в алгебре логики рассматривают переменные высказывания, которые не являются таковыми. Таким образом, вводятся понятия логических констант и переменных.

Так, если X, Y, Z – логические переменные то, применяя к ним операции конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания, можно получить формулы алгебры логики.

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

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

Рассмотренные выше логические выражения определяют основные функции двух переменных f(x, y) формулами: x  y, x  y, х  у, х  у,x. Ниже приведена их таблица истинности (табл. 2.1).

Таблица 2.1. Таблица истинности основных функций

Выполнять логические операции нужно в следующем порядке:

1. отрицание ( );

2. конъюнкция ();

3. дизъюнкция ();

4. импликация ();

5. эквивалентность ().

Скобки, как и в обычной алгебре, меняют этот порядок действий. Поэтому выражение в скобках вычисляется в первую очередь, т.е. имеет более высокий приоритет.

Пример 1. ФормулуF=xyzследует понимать так:

F = (x  y)  z.

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

Пример 2.Следующие две формулы:

F₁ =y  z и F₂ = (( x  y ) z)  ( x  y )

являются равносильными. Они определяют одну и ту же функцию f (x, y, z), что следует из таблицы 2.2.

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

Таблица 2.2. Таблица для равносильных формул

2.1.4. Логические функции

Функция f(x₁, х₂, ..., x_n), принимающая логическое значение (1 или 0) и за­висящая от логических переменных, называетсялогическойфункцией.Логическую функцию можно представить в виде отображенияf:Eⁿ  E, где множествоEⁿ =E  E  …  E есть декартово произ­ведение всех упорядоченных наборов (x₁, х₂, ..., x_n) таких, чтоx_i  E,i= 1,2,…,n.

Таким образом, область определения логической функции – сово­купность всевозможных n-мерных наборов из нулей и единиц, а для её задания достаточно указать, какие значения функции соответст­вуют каждому из наборов (табл. 2.3).

На­боры в таблице будем располагать в порядке возрастания их номера N.Такой порядок расположения наборов называ­етсястандартнымилиестественным.

При таком порядке каждому набору α = (α₁, …, α_n), где α_i есть 0 или 1, ставится в соответствие целое число

N = α₁2^n-1+ … + α_n-12¹+ α_n.

Наборам (0, 0, ...,0, 0), (0, 0, ..., 0, 1), ..., (1, 1, ..., 1, 1) соот­вет­ствуют числа N = 0, 1,..., 2ⁿ-1. Количество входных наборов для функции n переменных равно k = 2ⁿ.

Таблица 2.3. Задание логической функции