Основные понятия алгебры логики.

Основы логики

Основные понятия алгебры логики. Логические выражения и логические операции.

Термин «логика» происходит от древнегреческого logos – «слово, мысль, понятие, рассуждение, закон».

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

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

Анализ и проектирование логических схем опираются на законы алгебры логики.

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

Логические методы применяются и при работе с базами данных.

Логика – это наука о законах и формах мышления. Она изучает абстрактное мышление как средство познания объективного мира.

Этапы развития логики

Первые учения о формах и способах рассуждений возникли в странах Дальнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель (384–322 гг. до н.э.), который впервые отделил логические формы речи от ее содержания.

В XVII веке немецкий ученый и философ Готфрид Вильгельм Лейбниц (1646 – 1716) попытался построить первые логические исчисления, усовершенствовал и уточнил логические символы.

На фундаменте, заложенном Лейбницем, другой великий математик, англичанин Джордж Буль (1815-1864) воздвиг здание новой области науки – математической логики.

Начальный раздел математической логики называют алгеброй логики или Булевой алгеброй.

Алгебра логики

С точки зрения устройства ЭВМ нас интересует алгебра логики, в которой не рассматривается конкретное содержание основного понятия логики – высказывания, а важно только истинно оно или ложно.

Основным объектом в логике является высказывание.

Высказывание – это повествовательное предложение,

о котором можно сказать истинно оно или ложно.

Высказывание называется

Высказывание называется составным ,

если оно состоит из простых высказываний,

соединенных логическими связками:

И, ИЛИ, частицей НЕ

простым ,

если никакая его часть сама

не является высказыванием.

Основные понятия логики:

Утверждение – высказывание, которое требуется доказать или опровергнуть.

Например: «Сумма внутренних углов треугольника равна 180 0 »

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

Например: «Если хотите начать работать на компьютере, то необходимо сначала включить электропитание»

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

Например: «Все металлы электропроводны». «Ртуть является металлом». Путем умозаключения можно сделать вывод, что «Ртуть электропроводна».

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

Например: (А ۸ (В ۷ С))

Простые высказывания обозначают

заглавными латинскими буквами

A, B, C…X, Y, Z и называют

логическими переменными

Значения высказываний

ИСТИНА или ЛОЖЬ обозначают

соответственно цифрами 1 и 0

и называют логическими величинами

Составные высказывания называются

логическими выражениями и включают

в себя логические переменные,

операции логики и скобки для изменения

порядка действий операций

3» B = «7 = 3» C = «7 ≠ 3» D = «B ۸ C» = «(7 = 3) ۸ (7 ≠ 3)» На языке алгебры логики эти высказывания можно записать так: A = ИСТИНА = 1 B = ЛОЖЬ = 0 C = ИСТИНА = 1 D = ЛОЖЬ = 0" width="640"

Примеры:

Рассмотрим следующие высказывания:

• A = «7 3»
• B = «7 = 3»
• C = «7 ≠ 3»
• D = «B ۸ C» = «(7 = 3) ۸ (7 ≠ 3)»

На языке алгебры логики эти высказывания можно записать так:

A = ИСТИНА = 1

B = ЛОЖЬ = 0

C = ИСТИНА = 1

D = ЛОЖЬ = 0

Обозначение высказываний

A – Это утро ясное.

B – Это утро тёплое.

простые высказывания (элементарные)

Любое высказывание либо ложно (0) либо истинно (1)

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

A и B

Это утро ясное и тёплое.

Это утро ясное и оно не тёплое.

Это утро не ясное или оно тёплое.

A и не B

не A или B

Операция И ( логическое умножение, конъюнкция)

Высказывание " A и B " истинно тогда и только тогда, когда А и B одновременно истинны.

A

B

А и B

0

0

0

0

0

1

0

1

0

1

1

1

Примеры:

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

• Ленинград расположен на Неве и 2 + 3 = 5
• 7 – простое число и 9 – простое число
• 2 * 2 = 5 и 2 * 2 ≥ 3
• Книга – источник информации и 5 не больше 8

Ответ: истинными высказываниями являются: 1, 4

Операция ИЛИ ( логическое сложение, дизъюнкция)

Высказывание " A или B " ложно тогда и только тогда, когда А и B одновременно ложны

A

B

А или B

0

0

0

1

0

1

1

1

0

1

1

1

5 Луна – спутник Марса или Луна – спутник Земли Microsoft Word – текстовый редактор или Paint – графический редактор Ответ: истинными высказываниями являются: 1, 3, 4" width="640"

Примеры:

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

• 7 – простое число или 9 – простое число
• 2 или 2 5
• Луна – спутник Марса или Луна – спутник Земли
• Microsoft Word – текстовый редактор или Paint – графический редактор

Ответ: истинными высказываниями являются: 1, 3, 4

Операция НЕ ( инверсия, отрицание)

Если высказывание A истинно, то " не А " ложно,и наоборот.

А

не А

0

1

1

0

Примеры:

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

• Волга впадает в Каспийское море.
• Число 28 не делится на число 7.
• 6 3.
• 4 ≤ 5.

Базовый набор операций

С помощью операций И, ИЛИ и НЕ можно реализовать любую логическую операцию.

ИЛИ

И

НЕ

базовый набор операций

17

B " истинно, если не исключено, что из А следует B . A 0 B А = B 0 0 1 1 1 0 1 1 1 0 1" width="640"

Импликация, логическое следование ("если …, то …")

Высказывание " A = B " истинно, если не исключено, что из А следует B .

A

0

B

А = B

0

0

1

1

1

0

1

1

1

0

1

Примеры:

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

• Если 12 делится на 6, то 12 делится на 3.
• Если 11 делится на 6, то 11 делится на 3.
• Если 15 делится на 10, то 15 делится на 2.
• Если 15 делится на 3, то 15 делится на 6.

Ответ: истинными высказываниями являются: 1, 2, 3

Эквиваленция, равнозначность ("тогда и только тогда, …")

Высказывание " A  B " истинно тогда и только тогда, когда А и B равны.

A

0

B

А  B

0

0

1

1

1

1

0

0

0

1

1

Примеры:

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

• 12 делится на 6 тогда и только тогда, когда 12 делится на 3.
• 11 делится на 6 тогда и только тогда, когда 11 делится на 3.
• 15 делится на 6 тогда и только тогда, когда 15 делится на 3.
• 15 делится на 5 тогда и только тогда, когда 15 делится на 4.

Ответ: истинными высказываниями являются: 1, 2

Порядок выполнения операций

• Выражение в скобках
• Инверсия
• Конъюнкция
• Дизъюнкция, импликация, эквивалентность
• Операции отношения ( , ≤ , ≥ , = , ≠ )

В А ↔ В А ۸ В 1 1 0 А ۷ В 0 А 1 В 0 0 0 0 0 ¯ А 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 0 0" width="640"

Объединенная таблица истинности

А = В

А ↔ В

А ۸ В

1

1

0

А ۷ В

0

А

1

В

0

0

0

0

0

¯ А

1

0

0

1

0

1

1

1

1

1

1

0

1

1

1

1

0

0

Пример 1.

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

Проанализируем составное высказывание.

оно состоит из следующих простых высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдет на рыбалку», обозначим их через логические переменные:

А= «Петя поедет в деревню»;

В = «Будет хорошая погода»;

С = «Он пойдет на рыбалку».

Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки: F=A& (B → C).

Упражнение 2

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

А - «Число 10 – четное»;

В - «Волк травоядное животное».

Составьте из них все возможные составные высказывания и определите их истинность.

Решение:

А v В

¬ А

¬ В

А→В

А↔В

А&В

ЛОЖЬ (0)

ИСТИНА (1)

ЛОЖЬ (0)

ИСТИНА (1)

ЛОЖЬ (0)

ЛОЖЬ (0)

В Если Маша сестра Саши, то Саша – брат Маши. А = В Водительские права можно получать тогда и только тогда, когда тебе исполнится 18 лет. А↔В На компьютере можно выполнить вычисления или набрать текст. А v В" width="640"

Упражнение 3

Запишите высказывания в виде логических выражений:

• Число 13 нечетное и двузначное.

А&В

• Неверно, что корова хищное животное.

¬ А

• На уроке информатики ученики выполняли практическую работу и сообщали результаты учителю.

А&В

• Если число делится на 2, то оно четное.

А = В

• Если Маша сестра Саши, то Саша – брат Маши.

А = В

• Водительские права можно получать тогда и только тогда, когда тебе исполнится 18 лет.

А↔В

• На компьютере можно выполнить вычисления или набрать текст.

А v В

Упражнение 5

Найдите значение логических выражений:

• F=(0v0)v(1v1)

2. F=(1v1)v(1v0)

3. F=(0&0)&(1&1)

4. F= (1v1)v(¬0&1)

• (ответ: 1)
• (ответ: 1)
• (ответ: 0)
• (ответ: 1)