uzluga.ru
добавить свой файл


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


Логика

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

Основные формы мышления –

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

Алгебра логики появилась в середине XIX века в трудах английского математика Джорджа Буля. Он начал решать логические задачи алгебраическими методами.

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



Логические высказывания

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



Логические высказывания

Например:

«3х3 = 9» - истинное высказывание.

«Борак Обама– студент КБК 6» - ложное.



Логические высказывания

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

-Пример: 6- четное число

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

-Пример: Рим – столица Франции

Тоже высказывание, только ложное.

Логические высказывания

-Пример: Заходите завтра

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

Приведите примеры истинных, ложных логических высказываний и примеры, не являющиеся логическими высказываниями

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

Логические высказывания делятся на простые (элементарные) и составные.

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

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

Пример: «Петров - врач» , «Петров - шахматист».

При помощи связки «и» получаем составное высказывание «Петров – врач и шахматист»

При помощи связки «не» получаем составное высказывание «Петров – не врач»

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

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



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

Пример:

А=«Петров - врач»

В= «Петров - пожарный».

Тогда

С= А или В

С=«Петров – врач или пожарный»

D= А и не В

D=«Петров – врач и не пожарный»

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

Логические переменные могут принимать только два значения 1 и 0.

Если высказывание, определяющее логическую переменную – истинно, то переменная равна 1, если ложно, то 0.

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

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

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

В нашем случае первое высказывание истинно = 1), а второе ложно (В = 0).

Логические операции

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

Операция конъюнкции

Логическая связка И

Обозначение &, ^, •

F = A ^ B

В языках программирования and;

Название: Логическое умножение.

Значение функции F истинно тогда и только тогда, когда истинны и А и В.



Операция конъюнкции

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



Операция дизъюнкции

Логическая связка ИЛИ

Обозначение v

F = A v B

В языках программирования or;

Название: Логическое сложение.

Значение функции F ложно тогда и только тогда, когда ложны и А и В.



Операция дизъюнкции

Таблица истинности для операции логического сложения



Операция инверсии

Логическая связка НЕ

Обозначение

F = A

Название: Логическое отрицание.

Значение функции F ложно, когда А истинно, и истинно, когда А ложно.



Операция инверсии

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



Операция импликации

Логическая связка ЕСЛИ, ТО

Обозначение 

F = A  B

Название: Логическое следование.

Значение функции F ложно тогда и только тогда, когда А – истинно, а В - ложно.



Операция импликации

Таблица истинности для операции логического следования



Операция эквивалентность

Логическая связка ТОГДА И ТОЛЬКО ТОГДА, КОГДА

Обозначение 

F = A B

Название: Логическое тождество.

Значение функции F истинно тогда и только тогда, когда ложны А и В оба истинны или А и В оба ложны.



Операция ЭКВИВАЛЕНТНОСТИ

Таблица истинности



Таблица истинности

Решать логические формулы удобно при помощи таблицы истинности.

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

Таблица истинности

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

1. Количество строк в таблице = 2N, где N – количество переменных.

2. Количество столбцов = количество переменных + количество логических операций.

Таблица истинности

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

3. Установить последовательность выполнения логических операций.

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

5. Заполнить таблицу 1 и 0.

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

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

Но для уменьшения числа скобок договорились о приоритетах.
  • отрицание

  • умножение

  • сложение

  • следование



Пример



Пример



Пример



Пример



Пример



Самостоятельно