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

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

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

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

Логические высказывания Истинным будет высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Ложным будет высказывание, если оно противоречит реальной действительности. Например : «3 х 3 = 9» - истинное высказывание. « Борак Обама – студент КБК 6» - ложное.

Логические высказывания Не всякое предложение является логическим высказыванием. - Пример : 6- четное число следует считать высказыванием, т. к. оно истинное - Пример : Рим – столица Франции Тоже высказывание, только ложное.

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

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

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

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

Логические переменные Пример : А =« Петров - врач » В = « Петров - пожарный ». Тогда С = А или В С =« Петров – врач или пожарный » D= А и не В D=« Петров – врач и не пожарный »

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

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

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

Операция конъюнкции Логическая связка И Обозначение &, ^, F = A ^ B В языках программирования and; Название : Логическое умножение. Значение функции F истинно тогда и только тогда, когда истинны и А и В.

Операция конъюнкции Таблица истинности для операции логического умножения ABF=A^B

Операция дизъюнкции Логическая связка ИЛИ Обозначение v F = A v B В языках программирования or; Название : Логическое сложение. Значение функции F ложно тогда и только тогда, когда ложны и А и В.

Операция дизъюнкции Таблица истинности для операции логического сложения ABF=AvB

Операция инверсии Логическая связка НЕ Обозначение F = A Название : Логическое отрицание. Значение функции F ложно, когда А истинно, и истинно, когда А ложно.

Операция инверсии Таблица истинности для операции логического отрицания A F=A 01 10

Операция импликации Логическая связка ЕСЛИ, ТО Обозначение F = A B Название : Логическое следование. Значение функции F ложно тогда и только тогда, когда А – истинно, а В - ложно.

Операция импликации Таблица истинности для операции логического следования AB F=A B

Операция эквивалентность Логическая связка ТОГДА И ТОЛЬКО ТОГДА, КОГДА Обозначение F = A B Название : Логическое тождество. Значение функции F истинно тогда и только тогда, когда ложны А и В оба истинны или А и В оба ложны.

Операция ЭКВИВАЛЕНТНОСТИ Таблица истинности AB F=A B

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

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

Таблица истинности Алгоритм построения таблицы истинности 3. Установить последовательность выполнения логических операций. 4. Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных. 5. Заполнить таблицу 1 и 0.

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

Пример XYYF=X ^ Y построить таблицу истинности для выражения F=X ^ Y

Пример построить таблицу истинности для выражения F= ^ x x v y y

Пример построить таблицу истинности для выражения F= y xz ^ ^ ^z

Пример построить таблицу истинности для выражения ABС

Пример построить таблицу истинности для выражения F= y xz ^ ^ ^z

Самостоятельно построить таблицы истинности для выражений

AB неАнеВ 3*4 не

AD Не А 2+3 Не

ABC Не B 4*3 Не 5 1*

ADC Не A Не D 4+5 Не