Алгебра логики (булева алгебра)

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

Джордж Буль

Логическое высказывание (суждение ) — это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Так, например, предложение 

" Трава зеленая" следует считать высказыванием, так как оно истинное.

 

Предложение " Лев - птица" тоже высказывание, так как оно ложное.

 

 

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

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

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

Так, например, из элементарных  высказываний "Петров — врач", "Петров — шахматист" при помощи связки "и" можно получить составное высказывание "Петров — врач и шахматист", понимаемое как "Петров — врач, хорошо играющий в шахматы".

 

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

Упражнение №3 Из двух простых суждений постройте сложное суждение.

1. Марина старше Светы. Оля  старше Светы.

2. Иван – сын Петра. Иван  – внук Петра.

3. Одна половина класса изучает  английский язык. Вторая половина  класса изучает немецкий язык.

4. В кабинете есть учебники.  В кабинете есть справочники.

5. Слова в этом предложении  начинаются на букву Ч. Слова  в этом предложении начинаются  на букву А.

6. Часть туристов любит чай.  Остальные туристы любят молоко.

7. Синий кубик меньше красного.  Синий кубик меньше зеленого.

8. Х<6, X>2.

9. Летом я поеду в деревню.  Летом я поеду в туристическую  поездку.

 

Чтобы обращаться к  логическим высказываниям, им назначают  имена.

Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В — высказывание "Тимур летом отправится в горы".

Тогда составное высказывание    "Тимур летом побывает и на море,  и в горах"   можно кратко записать как     А и В.  Здесь   "и"  — логическая связка, А,   В   — логические переменные, которые могут принимать только два значения - "истина"  или "ложь", обозначаемые, соответственно, "1" и  "0".

Упражнение №1 Определите истинность  суждений:

 

• Наполеон был французским императором.
• Чему равно расстояние от Земли до Марса ?
• Киев – столица Украины.
• Некоторые рыбы – хищники.
• Внимание! Посмотрите направо.
• Электрон – элементарная частица.
• Не нарушайте правила дорожная движения!
• Полярная Звезда находится в созвездии Малой Медведицы.
• Все ребята умеют плавать

Типы суждений

(высказываний)

 

Общие

 

Частные

 

Единичные

 

Начинается со слов:

все,

всякий,

 каждый,

 ни один.

 

Начинается со слов

некоторые,

большинство,

не все и т.п.

 

Все остальные

Упражнение №2 Определить тип суждения:

Все рыбы умеют плавать.

Некоторые медведи – бурые.

Буква А – гласная.

Не все книги содержат полезную  информацию.

Кошка является домашним животным.

Все лекарства приятны на  вкус.

Некоторые лекарства приятны  на вкус.

Не всё то золото, что блестит.

Все хорошо, что хорошо кончается.

Часть народов России принадлежит  к монгольской расе.

Ни один внимательный человек  не совершит оплошность.

Некоторые ученики – двоечники.

Мой кот страшный забияка.

Отдельные животные не имеют  легких.

Любой неразумный человек ходит  на руках.

У некоторых змей нет ядовитых  зубов.

Многие растения обладают целебными  свойствами.

Все металлы проводят тепло.

Рыбы дышат жабрами.

Многие из почтенных людей  несчастны.

Только один металл жидкий.

Автор “Гулливера” жил в  Англии.

Не все званные избраны.

Ни один из римских рабов  не обладал гражданским правом.

 

 

Операции над логическими

высказываниями

Высказывание А истинно, когда A ложно, и ложно, когда A истинно.

 

Пример. "Луна — спутник Земли" (А); "Луна — не спутник Земли" (А).

 

 

НЕ 

  

Операция, выражаемая словом "не", называется инверсией или отрицанием и обозначается чертой над высказыванием.  

И   

Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой " ^. " (может также обозначаться знаками /\ или &).

Высказывание А · В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Например, высказывание

  "10 делится на 2 и 5 больше 3"   истинно, а высказывания    

 "10 делится на 2 и 5 не больше 3",  

"10 не делится на  2 и 5 больше 3",    

"10 не делится на  2 и 5 не больше 3"   -  ложны.

 

 

ИЛИ   

Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом).

Высказывание А v В ложно  тогда и только тогда, когда  оба высказывания А и В ложны.

Например, высказывание  

 "10 не делится на 2 или 5 не больше 3"   ложно,     а высказывания

"10 делится на 2  или 5 больше 3",

  "10 делится на 2 или 5 не больше 3",

 "10 не делится на 2 или 5 больше 3"—   истинны.

 

ЕСЛИ-ТО  

 Операция, выражаемая связками “

если ..., то", 

 "из ... следует", 

 "... влечет ...",  называется импликацией (лат. implico — тесно связаны) и обозначается знаком . Высказывание   А       В ложно тогда и только тогда, когда  А  истинно,  а  В  ложно.

  

РАВНОСИЛЬНО  

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

Импликацию можно выразить через

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

А   В = А v В

Эквиваленцию можно выразить через

Отрицание, дезъюнкцию и конъюнкцию

А   В = (А v В) ^ (B v A)

 

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

математики

 

в основе

 

число, переменная

 

логики

 

высказывание

(логическая переменная)

Сколько различных чисел существует?

Сколько различных переменных  существует?

Какие значения могут принимать  логические переменные?

Над числами и переменными  мы производим арифметические  действия 

Над переменными алгебраические  преобразования

Над высказываниями (логическими  переменными) мы можем производить  …?

…логические операции

 

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

КОНЪЮНКЦИЯ

 

ЛОГИЧЕСКОЕ УМНОЖЕНИЕ

 

ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ  ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ СОЮЗА

 

В прямоугольнике противоположные  стороны равны и параллельны

 

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

A

 

B

 

F = A ^ B

 

0

 

0

 

0

 

0

 

1

 

0

 

1

 

0

 

0

 

1

 

1

 

1

 

КОНЪЮНКЦИЯ

 

ЛОГИЧЕСКОЕ УМНОЖЕНИЕ

ДИЗЪЮНКЦИЯ

 

ЛОГИЧЕСКОЕ СЛОЖЕНИЕ

 

ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ  ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ СОЮЗА

 

Все положительные числа  больше отрицательных или больше 0

 

Все положительные числа  больше 1 или больше нуля

A

 

B

 

F = A ν B

 

0

 

0

 

0

 

0

 

1

 

1

 

1

 

0

 

1

 

1

 

1

 

1

 

ДИЗЪЮНКЦИЯ

 

ЛОГИЧЕСКОЕ СЛОЖЕНИЕ

ОТРИЦАНИЕ (ИНВЕРСИЯ)

 

ОПРЕДЕЛЯЕТ СОЕДИНЕНИЕ ДВУХ  ВЫСКАЗЫВАНИЙ С ПОМОЩЬЮ ЧАСТИЦЫ

 

А - «На улице идет дождь»

Тогда    ¬А -

                А -

 

«На улице нет дождя»

A

 

¬ А

 

0

 

1

 

1

 

0

 

ОТРИЦАНИЕ (ИНВЕРСИЯ)

Определите значение логического  выражения (0 или 1):

а) ¬А, если А – «число 6 – четное»

б) ¬А, если А – «Петр I – не был императором»

в) ¬А, если А – «металлы проводят ток»

г) ¬А, если А – «Москва – столица России»

д) ¬А, если А – «идет второй урок»

 

ОТРИЦАНИЕ (ИНВЕРСИЯ)

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

отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция

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

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

¬ А & ¬ B

 A & (B & C)

(A & B) ν (C &  ¬ D)

A ν ¬ D ν B

A ^ B ^ ¬ A

 

РЕШИМ ЗАДАЧИ

Алгоритм построения таблицы  истинности 

логической формулы:

 

• подсчитать количество переменных в формуле;
• определить число строк в таблице m = 2n, где n –количество переменных;
• подсчитать количество логических операций в формуле;
• установить последовательность выполнения логических операций с учетом скобок и приоритетов;
• определить количество столбцов в таблице:  число переменных + число операций;
• выписать наборы значений переменных в виде последовательности возрастающих n-разрядных двоичных чисел от 0 до 2n – 1;
• провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в п.4 очередностью выполнения

А