Урок "Логические выражения и операции"

 

 

Алгебра высказываний

 

Алгебра высказываний была разработана для того, чтобы можно было определять истинность или ложность состав­ных высказываний, не вникая в их содержание.

В алгебре высказываний суждениям (простым высказываниям) ставятся в соответствие логические переменные, обозначаемые прописными буквами латинского алфавита.

Рассмотрим два простых высказывания:

А = «Два умножить на два равно четырем».  В = «Два умножить на два равно пяти».

 

Высказывания, как уже говорилось ранее, могут быть истинными или ложными. Истинному высказыванию соответствует значение логической переменной 1, а ложному — значение 0. В нашем случае первое высказывание истинно (А = 1), а второе ложно (В = 0).

 

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

«истина» (1) и «ложь» (0).

 

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

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

Приведенное выше составное высказывание истинно, так как истинны входящие в него простые высказывания.

 

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

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

  

И  -   Логическое умножение (конъюнкция)

 

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

 

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

 

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

(1) «2 • 2 = 5 и 3 • 3 = 10»,     (2)        «2 • 2 = 5 и 3 • 3 = 9»,

(3) «2 -2 = 4 и 3 • 3 = 10»,      (4)        «2 • 2 == 4 и 3 • 3 = 9».

 

Перейдем теперь от записи высказываний на естествен­ном языке к их записи на формальном языке алгебры вы­сказываний (алгебры логики). В ней операцию логического умножения (конъюнкцию) принято обозначать значком «&» либо «/\». Образуем составное высказывание Р, которое получится в результате конъюнкции двух простых высказыва­ний:   F = А & В

 С точки зрения алгебры высказываний мы записали формулу функции логического умножения, аргументами кото­рой являются логические переменные А и В, которые могут принимать значения «истина» (1) и «ложь» (0).

 

Сама функция логического умножения F также может принимать лишь два значения «истина» (1) и «ложь» (0). Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов:

 

Таблица истинности функции логического умножения

 

А

В

F = А&В

По таблице истинности легко определить истинность со­ставного высказывания, образованного с помощью операции логического умножения. Рассмотрим, например, составное высказывание «2*2 = 4 и 3*3 = 10». Первое простое выска­зывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что логическая функция принимает значение ложь (F = 0), то есть данное составное высказывание ложно.

0

0

0

0

1

0

1

0

0

1

1

1

 

 

  

ИЛИ  -  Логическое сложение (дизъюнкция)

 

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

 

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

 

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

(1) «2 • 2 = 5 или 3 • 3 = 10»,    (2) «2 • 2 = 5 или 3-3 = 9»,

(3) «2 • 2 = 4 или 3 • 3 = 10»,     (4) «2 • 2 = 4 или 3-3 = 9».

Запишем теперь операцию логического сложения на формальном языке алгебры логики. Операцию логического сложения (дизъюнкцию) принято обозначать либо значком «V», либо знаком сложения «+». Образуем составное высказывание F, которое получится в результате дизъюнкции двух простых высказываний:  F = А V В

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

 

Таблица истинности функции логического сложения

 

А

В

F = А V В

 

Рассмотрим, например, составное высказывание «2*2 = 4 или 3*3 =10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что логическая функция принимает значение истина (F = 1), то есть данное составное высказывание истинно.

0

0

0

0

1

1

1

0

1

1

1

1

 

 

 

НЕ  -  Логическое отрицание (инверсия)

 

Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией.

 

         Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное — истинным.

 

Пусть А = «Два умножить на два равно четырем» — истинное высказывание, тогда высказывание F = «Два умно­жить на два не равно четырем», образованное с помощью операции логического отрицания, — ложно.

Операцию логического отрицания (инверсию) над логическим высказыванием А в алгебре логики принято обозна­чать А. Образуем высказывание F, являющееся логическим отрицанием А:  F = Ā = ¬А.

Истинность такого высказывания задается таблицей истинности функции логического отрицания:

 
Таблица истинности функции логического отрицания

 

 

А

F = ¬А

 

Например, высказывание «Два умножить на два не равно четырем» ложно (А = 0), а полученное из него в результате логического отрицания высказывание «Два умножить на два равно четырем» истинно (F = 1)

0

1

1

0

 

 

Логическое следование (импликация)

 

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

 

Логическая операция импликации «если А, то В», обозначается А → В и задается соответствующей таблицей истинности.

 

Таблица истинности логической функции «импликация»

А

B

F = А → В

0

0

1

0

1

1

1

0

0

1

1

1

 

 

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

 

Например, высказывание «Если число делится на 10, то оно делится на 5» истинно, так как истинны и первое вы­сказывание (предпосылка), и второе высказывание (вывод).

Высказывание «Если число делится на 10, то оно делится на 3» ложно, так как из истинной предпосылки делается ложный вывод.

 

Однако операция логического следования несколько отличается от обычного понимания слова «следует». Если пер­вое высказывание (предпосылка) ложно, то вне зависимости от истинности или ложности второго высказывания (выво­да) составное высказывание истинно. Это можно понимать таким образом, что из неверной предпосылки может следо­вать что угодно.

  

  

Логическое равенство (эквивалентность)

 

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

 

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

 

Таблица истинности логической функции эквивалентности

 

А

B

F  = А ≡ В

0

0

1

0

1

0

1

0

0

1

1

1

 

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

 

Рассмотрим, например, два высказывания: А = «Компьютер может производить вычисления» и В = «Компьютер включен». Составное высказывание, полученное с помощью операции эквивалентности, истинно, когда оба высказывания либо истинны, либо ложны:

«Компьютер может производить вычисления тогда и только тогда, когда компьютер включен».

«Компьютер не может производить вычисления тогда и только тогда, когда компьютер не включен».

Составное высказывание, полученное с помощью операции эквивалентности, ложно, когда одно высказывание истинно, а другое — ложно:

«Компьютер может производить вычисления тогда и только тогда, когда компьютер не включен».

«Компьютер не может производить вычисления тогда и только тогда, когда компьютер включен».