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

Логическая информация и основы логики

Подготовил:

учитель информатики

МАОУ СОШ № 19

Шорохова Светлана Сергеевна

Основатель логики

Основы логики были заложены работами ученого и философа Аристотеля (384 – 322 гг. до н.э.)

Он пытался найти ответ на вопрос «Как рассуждаем?», изучал правила мышления. Аристотель впервые дал систематическое изложение логики.

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

Так возникла формальная логика .

Основные понятия

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

Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта.

Высказывание ( суждение ) – это повествовательное предложение в котором что-либо утверждается или отрицается. По поводу любого высказывания можно сказать ИСТИННО оно или ЛОЖНО .

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

Пример 1

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

• Лед – твердое состояние воды.

• истинное высказывание

• истинное высказывание

• Треугольник – это геометрическая фигура.

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

• Привет!

• ложное высказывание

• Париж – столица Китая.

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

• Как тебя зовут?

Задание 1

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

• Число 6 – четное.
• Посмотрите на доску.
• Все роботы являются машинами.
• У каждой собаки есть хвост.
• Внимание!
• Кто отсутствует?
• Есть кошки, которые дружат с собаками.

Классификация высказываний

ВЫСКАЗЫВАНИЯ

ОБЩИЕ

ЕДИНИЧНЫЕ

ЧАСТНЫЕ

• Все
• Всякий
• Каждый
• Ни один

Во всех других случаях

• Некоторые
• Большинство
• И т.п.

Пример 2

Определить тип высказывания (общие, частное, единичное).

• (общее высказывание)

• (частное высказывание)

• (единичное высказывание)

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

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

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

Задание 2

Приведите по три примера каждого типа высказываний.

Определите их истинность.

Домашнее задание

• Приведите 5 предложений, определите, являются ли данные предложения высказываниями. Определите их истинность.

• Привести по три примера каждого типа высказываний.

• Подготовиться к самостоятельной работе.

Логические величины, операции, выражения

Логические величины

Логические величины: понятия, выражаемые словами: ИСТИНА , ЛОЖЬ (true, false).

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

Основные определения

Логическая константа : ИСТИНА или ЛОЖЬ.

Логическая переменная : символически обозначенная логическая величина. Следовательно, если известно, что А, В, Х, Y и пр. – переменные логические величины, то это значит, что они могут принимать значения только ИСТИНА или ЛОЖЬ.

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

Основные логические операции:

• Инверсия (отрицание);
• Конъюнкция (логическое умножение);
• Дизъюнкция (логическое сложение);
• Импликация (следование);
• Эквивалентность (равнозначность.

Отрицание

В русском языке этой связке соответствует частица НЕ (в некоторых высказываниях применяется оборот «неверно, что …»). Отрицание – унарная (одноместная) операция; записывается в виде: ¬ А или Ā.

А

0

Ā

1

1

0

Пример (отрицание)

Рассмотрим сложное высказывание: «Неверно, что 4 делится на 3».

Обозначим через А простое высказывание:

А – «4 делится на 3»

Тогда соответствующая логическая формула имеет вид: ¬А или Ā.

Когда данное высказывание истинно?

Конъюнкция

Конъюнкция (логическое умножение). В русском языке она выражается союзом И. В математической логике используется знаки & или ^. Конъюнкция – двухместная операция; записывается в виде А ^ В. Значение такого выражения ЛОЖЬ, если значение хотя бы одного операндов ложно.

А

0

В

А ^ В

0

0

0

1

1

1

0

0

0

1

1

Пример (конъюнкции)

Рассмотрим сложное высказывание: «Число 6 делится на 2, и число 6 делится на 3». Представить данное высказывание в виде логической формулы.

Разделим данное сложное высказывание на два простых: А – «число 6 делится на 2»

В – «число 6 делится на 3».

Тогда соответствующая логическая формула имеет вид: А ^ В (А & В). Очевидно, её значение – ИСТИНА.

Дизъюнкция

Дизъюнкция (логическое сложение). В русском языке этой связке соответствует союз ИЛИ. В математической логике она обозначается v. Дизъюнкция – двухместная операция; записывается в виде: А v В. Значение такого выражения будет ИСТИНО, если значение хотя бы одного из операндов истинно.

А

0

В

0

0

А v В

0

1

1

1

1

0

1

1

1

Пример (дизъюнкция)

Рассмотрим сложное высказывание: «Летом я поеду в деревню или в туристическую поездку».

Разделим данное сложное высказывание на два простых: А – «летом я поеду в деревню»

В – «летом я поеду в туристическую поездку».

Тогда соответствующая логическая формула имеет вид: А v В.

Когда данное высказывание истинно?

Пример 1

Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ»:

А – «Все ученики изучают математику»

В – «Все ученики изучают литературу»

 Все ученики изучают математику и литературу. (А ^ В)

Пример 2

Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ»:

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

В – «Слова в этом предложении начинаются на букву А»

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

2. " width="640"

Задание 1

Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ»:

• Марина старше Светы. Оля старше Светы.
• Одна половина класса изучает английский язык. Вторая половина класса изучает немецкий язык.
• В кабинете есть учебники. В кабинете есть справочники.
• Часть туристов любит чай. Остальные туристы любят молоко.
• Х = 3, X2.

B , где  А  – условие,  В  – следствие. Например: А=" На улице светит солнце " В=" На улице ясная погода " Используя оборот-связку « если..., то... », получим " Если светит солнце,  то  на улице    ясная погода ". Высказывание А Если не светит солнце,  то  на улице    пасмурная погода Если не светит солнце,  то  на улице    ясная погода В 0 А=B Если светит солнце,  то  на улице    пасмурная погода 0 0 Если светит солнце,  то  на улице    ясная погода 1 1 1 1 0 1 0 1 1 " width="640"

Импликация

ИМПЛИКАЦИЯ   (от лат.  implicatio  – тесно связывать) – логическое следование . В естественном языке ему соответствует оборот  " если . . ., то . . . ". Обозначение в алгебре высказываний:  А=B , где  А  – условие,  В  – следствие.

Например: А=" На улице светит солнце "

В=" На улице ясная погода "

Используя оборот-связку « если..., то... », получим " Если светит солнце,  то  на улице    ясная погода ".

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

А

Если не светит солнце,  то  на улице    пасмурная погода

Если не светит солнце,  то  на улице    ясная погода

В

0

А=B

Если светит солнце,  то  на улице    пасмурная погода

0

0

Если светит солнце,  то  на улице    ясная погода

1

1

1

1

0

1

0

1

1

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

ЭКВИВАЛЕНТНОСТЬ   (от лат.  aequivalens  – равноценное) –  логическое равенство . Обозначение в алгебре высказываний:  АB . В естественном языке ему соответствует оборот  " ... тогда и только тогда, когда ... ".

Например: А=" На улице ясная погода "

В=" На улице светит солнце "

Используя, логическую связку " ...тогда и только тогда, когда... ".  Получим " На улице ясная погода  тогда и только тогда, когда  светит солнце ".

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

А

На улице пасмурная погода  тогда и только тогда, когда  не светит солнце

В

На улице пасмурная погода  тогда и только тогда, когда  светит солнце  

0

АB

На улице ясная погода  тогда и только тогда, когда не  светит солнце  

0

0

На улице ясная погода  тогда и только тогда, когда  светит солнце  

1

1

1

0

0

1

0

1

1

Логические выражения, правила составления логических выражений

• Логическая переменная  – это простое высказывание, содержащее  только одну мысль . Ее символическое обозначение – латинская буква (например, A, B, X, Y и т.д.). Значением логической переменной могут быть только константы ИСТИНА ( 1 ) и ЛОЖЬ ( 0 ). На основании простых высказываний могут быть построены  составные высказывания .
•     Логическая функция  - составное высказывание, которое содержит  несколько простых мыслей , соединенных между собой с помощью логических операций.
• Ее символическое обозначение –  F (A, B, …) .
• Логические операции  – логическое действие. 

C.   Пример 5 Записывать в виде логического выражения следующее высказывание: « Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку ».   1.  Проанализируем составное высказывание . Оно состоит из следующих простых высказываний: « Петя поедет в деревню », « Будет хорошая погода », «Петя пойдет на рыбалку». Обозначим их через логические переменные: А = Петя поедет в деревню; В = Будет хорошая погода; С = Петя пойдет на рыбалку.   2.  Запишем высказывание в виде логического выражения , учитывая порядок действий. Если необходимо, расставим скобки:  F=A&(B=C) . " width="640"

• Пример 4
•     1.  Проанализируем составное высказывание  " Если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог ".
• Обозначим буквой A высказывание:  "Купить яблоки" , буквой B - высказывание:  "Купить абрикосы",  буквой C - высказывание:  "Испечь пирог".
• 2.  Запишем высказывание в виде логического выражения , высказывание " Если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог " формализуется в виде формулы:  F=(A v B)=C.
•  
• Пример 5
• Записывать в виде логического выражения следующее высказывание: « Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку ».
•  
• 1.  Проанализируем составное высказывание . Оно состоит из следующих простых высказываний: « Петя поедет в деревню », « Будет хорошая погода », «Петя пойдет на рыбалку». Обозначим их через логические переменные:
• А = Петя поедет в деревню;
• В = Будет хорошая погода;
• С = Петя пойдет на рыбалку.
•  
• 2.  Запишем высказывание в виде логического выражения , учитывая порядок действий. Если необходимо, расставим скобки:  F=A&(B=C) .

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

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

• Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных + строка заголовков столбцов).
• Выяснить количество столбцов (вычисляется как количество переменных + количество логических операций).
• Установить последовательность выполнения логических операций.
• Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных.
• Заполнить таблицу истинности по столбцам.
• Записать ответ.

Пр. 1   F=(AvB)&(¬Av¬B)

Пр. 2   F=XvY&¬Z .

Постройте таблицы истинности для следующих функций:

Логические основы устройства компьютера. Логические схемы

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

Логический элемент -  конъюнктор . Логическая операция И .

А

В

0

0

0

А ^ В

1

0

1

0

0

1

1

0

1

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

Логический элемент -  дизъюнктор . Логическая операция ИЛИ .

А

В

0

А v В

0

0

1

0

1

1

0

1

1

1

1

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

Логический элемент -  инвертор . Логическая операция НЕ .

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

А

0

Ā

1

1

0

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

• Логический элемент (вентиль) компьютера  — это часть электронной логичеcкой схемы, которая реализует элементарную логическую операцию.

• Логическими элементами компьютеров являются электронные схемы  И ,  ИЛИ ,  НЕ ,  И-НЕ ,  ИЛИ-НЕ  и другие (сумматор и триггер).

•    С помощью этих схем можно реализовать любую логическую функцию, описывающую работу устройств компьютера.

Алгоритм построения логических схем:

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

Пр. 1 F=¬XvY&X (X=1, Y=0)

Пр. 2 S=(AvB)& ¬(A&B)

Пр. 3 F=X&Yv¬(YvX)

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

1) F=AvB&¬C,         если A=1, B=1, C=1.

2) F = ¬(AvB&C),    если A=0, B=1, C=1.

3) F =¬AvB&C,        если A=1, B=0, C=1.

Запишите логическое выражение и найдите его значение (A=1; B=1; C=0):