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

2
Логические операции. Построение таблиц истинности

Урок № 3
Логические законы. Упрощение сложных высказываний

Хорошо думать — значит победить беспорядочность потока мыслей.
Густав Гийом

понятия логики

Урок № 1
Логика как наука.
Формы человеческого мышления

Урок № 2
Логические операции. Построение таблиц истинности

Урок № 3
Логические законы. Упрощение сложных высказываний

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

Урок № 1
Логика как наука.
Формы человеческого мышления

Урок № 2
Логические операции. Построение таблиц истинности

Урок № 3
Логические законы. Упрощение сложных высказываний

Логика как наука.
Формы человеческого мышления

Урок № 2
Логические операции. Построение таблиц истинности

Урок № 3
Логические законы. Упрощение сложных высказываний

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

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

Готфрид Вильгельм Лейбниц
(1646 - 1716 )

математики и логики XVI - XX веков, в том числе

М. В. Ломоносов

И. Кант

Г. Фреге

А. Тьюринг

Д. Гильберт

К. Гедель

А. Н. Колмогоров

П. С. Новиков

А. А. Марков

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

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

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

☞ в повседневных рассуждениях.

Практическое применение булевой алгебры

обработки и передачи информации.

Совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров

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

вращать кистями рук в одну и другую сторону. Повторить 4-5 раз.
Упражнение третье:
перевести взгляд быстро по диагонали: направо вверх - налево вниз, потом прямо вдаль на счет 1-6; затем налево вверх - направо вниз и посмотреть вдаль на счет 1-6. Повторить 4-5 раз.

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

Суждение (высказывание, утверждение) -форма мышления, в которой что-либо утверждается или отрицается о предметах, их свойствах или отношениях между ними.

и восклицательные предложения.
Предикаты (выражения о переменных) , в которых значения переменных не определены.

☜ Эта книга - информатика.
☜ Метеорологический прогноз.
☜ Как мелодичны вы, песни, Украины!
☜ Верно ли, что сегодня теплая погода?
☜ 5 +X =12
☜ X + Z < 1
☜ Число Y кратно 3

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

нескольких истинных суждений (посылок) по определенным правилам вывода получают суждение-заключение.

Некоторые люди имеют голубые глаза.
Вы были в театре?
Мойте руки перед едой.
Если будет дождь, то мы поедем за грибами.
Завтра я сдам экзамен, либо останусь на второй год.
Существую такие люди, которые не любят животных.
Завтра я пойду на каток.
Если я поеду туда, то смогу ли вернуться?
IF X>1 THEN Y=0

С
У
Ж
Д
Е
Н
И
Е

Н
Е
С
У
Ж
Д
Е
Н
И
Е

простые:

Если две прямые параллельны, то они пересекаются.
Идет дождь.
На следующем уроке будет либо контрольная работа, либо свободный урок.
Завтра или сегодня брат приедет к нам в гости.
Треугольники с равными сторонами не равнобедренны.
Завтра премьера в нашем театре.
Это число не простое.
Сегодня, завтра и каждый день я буду учиться.
7 + x ≥ x + c + 0,1 a
Число 4 больше числа 2.

С
Л
О
Ж
Н
Ы
Е

П
Р
О
С
Т
Ы
Е

двум прямым углам";
"верно ли, что  π=3,1415926...?";
"44>88";
"математическое доказательство";
"Z + 5 = 45".

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

И
С
Т
И
Н
А

Л
О
Ж
Ь

X2  - Y2;
"Любой ромб является параллелограммом";
"А3= А2, если А=1";
Если |А| = |В|, то А = В;
"Квадрат любого числа делится на 4";
"Меркурий - спутник Марса";
"Джордано Бруно - ученик Галилео Галилея";
"Не существует целого числа, куб которого оканчивается цифрой 2 ".

Укажите, какие из суждений являются частными, а какие общими:

Ч
А
С
Т
Н
Ы
Е

О
Б
Щ
И
Е

на 2-3 секунды, повторить упражнение 10 раз.
Упражнение второе:
часто-часто моргать глазами, повторить 10 раз.
Упражнение третье:
поднять глаза вверх, при этом голова остается в одном положении, задержать взгляд на 2-3 секунды, затем опустить глаза вниз и задержать взгляд на 2-3 секунды повторить упражнение 10 раз .

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

сказуемому или использования оборота речи «НЕВЕРНО, ЧТО...»

Обозначение: Ā, ¬А, не А, not А

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

Примеры инверсии:
А= «Неверно, что у меня есть приставка Dendy»
В= «Я не знаю китайского языка»

Инверсия высказывания истинная, когда высказывание ложно, и ложна, когда высказывание истинно.

(а также «А», «НО» )

Обозначение: А и В, А^В, А & В, А*В, А and B, А∩ B

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

Примеры конъюнкции:
А= «Сегодня солнечный день и мы пойдем гулять»
В= «Богдан был победителем, а Степан занял второе место»

Конъюнкция двух высказываний истинная тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно высказывание ложно.

«ИЛИ» (нестрогая), «ЛИБО» (строгая)

Обозначение: А или В, АV В, А | В, А+В, А or B, А∪ B;
A∀B, A xor B

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

Примеры дизъюнкции:
А= «Снег пойдет ночью или утром»
В= «Он приедет сегодня либо завтра»

Дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно.

речи «ЕСЛИ …, ТО ...»

Обозначение: А → В, А⇒ В

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

Примеры импликации:
А= «Если число делится на 9, то оно делится на 3»
В= «Если на улице дождь, то асфальт мокрый»

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

речи «… ТОГДА И ТОЛЬКО ТОГДА, КОГДА ...»

Обозначение: А ↔ В, А⇔ В, А=В, А≡В, А~В

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

Примеры эквивалентности:
А= «Число кратно 3 тогда и только тогда, когда сумма цифр числа делится нацело на 3»
В= «Угол называется прямым тогда и только тогда, когда он равен 90°»

Эквивалентность двух высказываний истинна тогда и только тогда, когда оба высказывания истинны или оба ложны.

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

истинно

ложно

Импликация ложна

из истинного высказывания следует ложное высказывание

Эквивалентностьистинна

оба высказывания ложны или оба высказывания истинны

тогда
и
только
тогда,
когда

А; неверно, что А
и А, и В; как А, так и В; А вместе с В; А несмотря на В; А, в то время как В; А и В
А или В; А либо В; либо А, либо В; строго А или В
если А, то В; В, если А; В необходимо для А; А достаточно для В; А только тогда, когда В; В тогда, когда А; все А есть В
А эквивалентно В; А необходимо и достаточно для В; А тогда и только тогда, когда В

изменения порядка действий используются скобки.

Ā

Порядок вычисления:

Ā

C&D

АV В

А V В ⇒ С & D

А V В ⇒ С & D ⇔ Ā

инверсия

конъюнкция

дизъюнкция

импликация

эквивалентность

1

2

3

4

5

Ā

Порядок вычисления:

Ā

(В ⇒ C)

(В ⇒ С) & D

А V (В ⇒ С) & D

А V (В ⇒ С) & D ⇔ Ā

инверсия

импликация в скобках

конъюнкция

дизъюнкция

эквивалентность

1

2

3

4

5

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

Примеры сложных высказываний:

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

Если высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0).

Например, Компьютер включен, и компьютер выключен.

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

Например, Демократ - человек, исповедующий демократические убеждения.

меня будет свободное время, и я сдам экзамены, то я поеду отдыхать»
ложно.

сдам экзамены»
А = «Я поеду отдыхать»
B & Ē ? Ā

& Ē ? Ā

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

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

( на примере n=3):

& Ē ?Ā

тождественны самим себе.

А = А

было и не было присуще одному и тому же в одном и том же отношении. То есть невозможно что-то одновременно утверждать и отрицать.

А & Ā = 0

третьего не дано.

А + Ā = 1

исходное высказывание.

А = А

v 1 = 1

отрицание истины есть ложь.

1 = 0
А & 0 = 0
А & 1 = A

конъюнкции можно менять местами.

А v В = В v А

А & В = В & А

только операция конъюнкции, то можно пренебрегать скобками или произвольно их расставлять.

А v (В v C) = (А v В) v C

А & (В & C) = (А & В) & C

(А v C)

А & (В v C) = (А & В) v (А & C)

(А v В) = А или
(А v B) & B = А & B

А v В & B = А или
А v (А & В) = А или
(А & B) v B = А v B

отрицаний.

А v В = А & В или А v B = А & B

А & В = А v В или
А & B = А v B

В = (А v В) & (А v B)

А ⇔ В = (А & В) v (А & B)

А ⇔ В = (А ⇒ В) & (B ⇒ A)

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

v A

0 = Z & Z

B = B v B = B v B v B v B
C = C & C = C & C & C & C

E = E

- по свойствам констант;

- по закону исключения третьего;

- по закону исключения третьего;

- по законам идемпотентности;

- по закону двойного отрицания.

логику, был получен правильный ответ:
если изучал первый, то изучал и второй, но не верно, что если изучал третий, то изучал и второй.
Кто из учащихся изучал логику?

«Второй школьник изучал логику»
Р3 = «Третий школьник изучал логику»

=
= (P1 v P2) & (P3 v P2) =
= (P1 v P2) & (P3 & P2) =
= (P1 & P3 & P2) v (P2 & P3 & P2) =
= 0
= (P1 & P3 & P2)

закону дистрибутивности вынесем А за скобки:
А & B v A & B = А & (B v B) = А & 1 = A

Применим закон дистрибутивности:
(А v B) & (A v B) = А v (B & B) = А v 0 = A

Способ 2. Перемножим скобки на основании того же закона дистрибутивности:
(А v B) & (A v B) = А & А v А & B v B & А v B & B = А v А & (B v B) v 0 = А v A & 1 = А v А = A

& 1, а 1 распишем по закону исключения третьего как Y v Y, далее раскроем скобки:
X v X & Y = X & 1 v X & Y = X & (Y v Y) v X & Y= X & Y v v X & Y v X & Y.
Закон имподентности позволяет добавить в выражение любое из имеющихся в нем слагаемых. Добавим к полученному выражению X & Y и сгруппируем слагаемые:
X & Y v X & Y v X & Y = X & Y v X & Y v X & Y v X & Y = = (X & Y v X & Y) v (X & Y v X & Y) = X & (Y v Y) v Y & & (X v X) = X & 1 v Y & 1 = X v Y.

А & B

Добавим к последнему слагаемому С. Это делается стандартным способом: умножим А & B на 1, а 1 распишем как С v С:
A & C v B & C v A & B = A & C v B & C v A & B & 1 = A & C v v B & C v А & B & (C v C) = A & C v B & C v A & B & C v A & & B & C = A & C v A & B & C v B & C v A & B & C = = A & C & (1 v B) v B & C & (1 v А) = A & C v B & C

v Y = X & Y = X & Y

X & Z

В данном случае воспользуемся законом двойного отрицания:
X & Y v X & Y v X & Z = X & Y v X & Y v X & Z =
{раскроем одно отрицание}= (X & Y) & (X & Y) & (X & Z) =
= (X v Y) & (X v Y) & (X v Z) = {перемножим первую и вторую скобки, упростим, а третью скобку оставим без
изменения}= (X & X v X & Y v X & Y v Y & Y) & (X v Z) =
= (X & Y v X & Y) & (X v Z) = {перемножим скобки,
упростим}= X & X & Y v X & Y & Z v X & Y v X & Y & Z =
= X & Y & Z v X & Y = {применим закон де Моргана}= = X & Y & Z & (X v Y) = (X v Y v Z) & (X v Y)