Логические основы информатики

Например, высказывание «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый».

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

4. Импликация.

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

Импликация высказываний х, у обозначается символом х у, читается «если х, то у» или «из х следует у». Высказывание х называют условием или посылкой, высказывание у — следствием или заключением, высказывание х у - следованием или импликацией.

Логические значения операции импликации описываются следующей таблицей истинности:

x	x	х y
1	1	1
1	0	0
0	1	1
0	0	1

Например, высказывание «Если число 12 делится на 6, то оно делится  на 3», очевидно, истинно, так как  здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».  «Если 2 x 2=5,  то существует  баба  яга »

Употребление слов «если .,., то ...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание х ложно, то высказывание «Если х, то у» вообще не имеет смысла. Кроме того, строя предложение вида «если х, то у» в обыденной речи, мы всегда подразумеваем, что предложение у вытекает из предложения х. Употребление слов «если ..., то ...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается. 

5. Эквивалеация.

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

Эквиваленция высказываний х, у обозначается символом х у, читается «для того, чтобы х, необходимо и достаточно, чтобы y» или «х тогда и только тогда, когда у». Высказывания х, у называются членами эквиваленции. Логические значения операции эквиваленцин описываются следующей таблицей истинности:

х	y	х у
*1	1	1
1	0	0
0	1	0
0	0	1

Например, эквиваленция «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда  SP=SQ» является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ   SP = SQ » либо одновременно истинны, либо одновременно ложны. Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.

6. Сложение  по  модулю  два  .

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

    (8) 

x	y
0	0	0
0	1	1
1	0	1
1	1	0

 

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

Запись    читается  как «x  стрелка Пирса y».  Функция истина  тогда и  только тогда,  когда  ложны  обе  её переменные. 

x	y
0	0	1
0	1	0
1	0	0
1	1	0

Cтрелка  Пирса  противоположна  дизъюнкции,  и для неё справедливо: 

     (9)

8. Функция Шеффера.

Запись  x|y   читается  как   «x   штрих Шеффера y». Функция  ложна  тогда и только  тогда,  когда  оба  значения  переменных истинны.

x	y
0	0	1
0	1	1
1	0	1
1	1	0

Штрих  Шеффера  противоположна   конъюнкции,  и для неё справедливо:

                                                          (10)

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

   и  

Первое из них есть дизъюнкция конъюнкции х, у, а второе высказывание есть импликация, посылкой которой является высказывание х, а  заключением - отрицание дизъюнкции высказывания у и конъюнкции высказываний х, z.

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

Формулы алгебры логики будем обозначать большими буквами латинского алфавита А, В, С, ...

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

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

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

Например, для формулы    таблица истинности:

x	y		х&у
1	1	1	1	1
1	0	1	0	0
0	1	1	0	0
0	0	0	0	1

 

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

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

Равносильность формул будем обозначать знаком , а запись А В означает, что формулы А и В равносильны.

Например, равносильны формулы:

Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы:

 

Формула А называется тождественно ложной, если она принимает значение О при всех значениях входящих в нее переменных.

Например, тождественно ложна формула:

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно,

Между понятиями равносильности и  эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А В - тавтология, и обратно, если формула - тавтология, то формулы А и В равносильны.

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

Например, формула:      является функцией  трех переменных   .

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

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

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

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

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

 -единичная функция    -сложение  по  модулю 2

-дизъюнкция    -отрицание 

-импликация    функция сохранения второй переменной

- импликация    -стрелка Пирса

-функция Шеффера 

-функция  сохранения первой   

 переменной    

-эквивалентность   - конъюнкция

-отрицание     - нулевая функция

Формы представления логических функций.

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

• дизъюнктивная нормальная форма
• конъюнктивная нормальная форма.

 Дизъюнктивная нормальная форма (ДНФ) - это сумма произведений, образованных из переменных и их отрицаний. ДНФ не содержит скобок.

Например, формы_  - дизъюнктивная нормальная форма, a   - нет.

Конъюнктивная нормальная форма (КНФ) - это произведение сумм, состоящих из переменных и их отрицаний.

Например, формы ( a +b)c, ab(c +b), , а- конъюнктивные нормальные формы.

Теорема о ДНФ Всякая сложная логическая функция может быть сведена к ДНФ.

Для того чтобы сделать это, необходимо:

• записать булеву функцию в виде {+, •, -};
• с помощью законов де Моргана спустить черту отрицания до отдельных букв и по закону двойного отрицания уничтожить двойные черточки;
• с помощью первого закона дистрибутивности уничтожить все произведения сумм и провести поглошение.