Тема: Основные понятия математической логики

Скачать 0.75 Mb.

Название	Тема: Основные понятия математической логики
страница	2/8
Дата публикации	22.02.2015
Размер	0.75 Mb.
Тип	Решение

100-bal.ru > Математика > Решение

1 2 3 4 5 6 7 8

Тема: Преобразование логических выражений. Формулы де Моргана.

Про обозначения

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,, ¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (,, ¬), что еще раз подчеркивает проблему.

Что нужно знать:

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

¬ A, не A (отрицание, инверсия)

A  B, A и B (логическое умножение, конъюнкция)

A  B, A или B (логическое сложение, дизъюнкция)

A → B импликация (следование)

операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = ¬ A  B или в других обозначениях A → B =

если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
правила преобразования логических выражений (слайд из презентации «Логика»):

фактически это задание на применение законов де Моргана (хотя об этом нигде не говорится):

¬ (A  B) = ¬ A  ¬ B

¬ (A  B) = ¬ A  ¬ B

Пример задания:

Укажите, какое логическое выражение равносильно выражению A  ¬(¬B  C).

1) ¬A  ¬B  ¬C 2) A  ¬B  ¬C 3) A  B  ¬C 4) A  ¬B  C

Решение (вариант 1, использование законов де Моргана):

перепишем заданное выражение и ответы в других обозначениях:
заданное выражение
ответы: 1) 2) 3) 4)
посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана,

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

таким образом, правильный ответ – 3 .

Возможные ловушки и проблемы:

серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений с «закорючками», поэтому рекомендуется сначала внимательно перевести их в «удобоваримый» вид; при этом сразу становится понятно, что ответы 1 и 2 заведомо неверные
при использовании законов де Моргана часто забывают, что нужно заменить «И» на «ИЛИ» и «ИЛИ» на «И» (возможный неверный ответ )
расчет на то, что при использовании законов де Моргана инверсия сложного выражения по ошибке «просто пропадет», и все сведется к замене «ИЛИ» на «И» (неверный ответ )
иногда для решения нужно упростить не только исходное выражение, но и заданные ответы, если они содержат импликацию или инверсию сложных выражений

Решение (вариант 2, через таблицы истинности, если забыли формулы де Моргана):

перепишем заданное выражение в других обозначениях:
заданное выражение
ответы: 1) 2) 3) 4)
для доказательства равносильности двух логических выражений достаточно показать, что они принимают равные значения при всех возможных комбинациях исходных данных; поэтому можно составить таблицы истинности для исходного выражения и всех ответов и сравнить их
здесь 3 переменных, каждая из которых принимает два возможных значения (всего 8 вариантов, которые в таблице истинности записывают по возрастанию двоичных кодов – см. презентацию «Логика»)
исходное выражение истинно только тогда, когда и , то есть только при . (в таблице истинности одна единица, остальные – нули)
выражение истинно, если хотя бы одна из переменных равна нулю, то есть, оно будет ложно только при (в таблице истинности один нуль, остальные – единицы)
аналогично выражение ложно только при , а в остальных случаях – истинно
выражение истинно только при , а в остальных случаях – ложно
выражение истинно только при , а в остальных случаях – ложно
объединяя все эти результаты в таблицу, получаем:

A	B	C
0	0	0	0	1	1	0	0
0	0	1	0	1	1	0	0
0	1	0	0	1	1	0	0
0	1	1	0	1	0	0	0
1	0	0	0	1	1	0	0
1	0	1	0	1	1	0	1
1	1	0	1	1	1	1	0
1	1	1	0	0	1	0	0

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

Возможные проблемы:

сравнительно большой объем работы

Выводы:

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

Задачи для тренировки:

Укажите, какое логическое выражение равносильно выражению ¬(A  ¬B  C) ?

1) ¬A  B  ¬C 2) A  ¬B  C 3) ¬A  ¬B  ¬C 4) ¬A  B  ¬C

Какое логическое выражение равносильно выражению ¬ (A  B)  ¬C ?

1) ¬A  B  ¬C 2)(¬A  ¬B)  ¬C 3)(¬A  ¬B)  C 4) ¬A  ¬B  ¬C

Укажите, какое логическое выражение равносильно выражению ¬ (¬А  B)?

1) A  ¬B 2) ¬A  B 3) B  ¬A 4) A  ¬B

Какое логическое выражение равносильно выражению ¬(А  ¬B) ?

1) A  B 2) A  B 3) ¬A  ¬B 4) ¬A  B

Какое логическое выражение эквивалентно выражению ¬(¬A  ¬B)  C ?

1) (A  ¬B)  C 2) A  B  C 3) (A → ¬B) C 4) ¬(A  ¬B) C

Какое логическое выражение эквивалентно выражению A  ¬(¬B  ¬C)?

1) A  B  C 2) A  B  ¬C 3) A  (B  C) 4) (A  ¬B)  ¬C

Какое логическое выражение эквивалентно выражению ¬(A  B)  ¬C?

1) (A  B)  ¬C 2) (A  B)  C 3) (¬A  ¬B)  ¬C 4) (A  B)  C

Какое логическое выражение эквивалентно выражению ¬(A  ¬B)  ¬C?

1) A  B  C 2) ¬(A  B)  C 3) ¬(A  C)  B 4) ¬(A  C)  B

Какое логическое выражение эквивалентно выражению ¬(¬A  B)  ¬C?

1) (A  B)  ¬C 2) (A  B)  C 3) (A  ¬B)  ¬C 4) (A  ¬B)  ¬C

Какое логическое выражение эквивалентно выражению ¬(A  B) → C?

1) ¬A  B  C 2) A  B  C 3) ¬(A  B)  C 4) ¬A  ¬B  ¬C

A9 (базовый уровень, время – 2 мин)

1 2 3 4 5 6 7 8

Похожие:

	Тема: «Исследования Луны» Учитель физики моу «Каширская оош» Горчакова Елена Павловна Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...		Урок лекция План проведения урока Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...
	1. «Совершенные дизъюнктивные нормальные формы (сднф) и совершенные... Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим...		Урок 1 Тема урока : Логика как наука. Основные понятия математической логики Учебный курс (рабочая программа) «Логика научного исследования» для аспирантов очной и заочной форм обучения специальностей 09. 00....
	Программа дисциплины логика для специальности 080504. 65 Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...		Педагогическая психология среди других наук Общенаучная характеристика педагогической психологии Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...
	Развивающие игры как средство развития логического мышления младшего школьника Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...		Исследовательская работа «Влияние лунных фаз на рост, развитие и урожайность редиса и свеклы» Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...
	Проект программы XVII международного экологического телевизионного... Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...		Н. Г. Чернышевский Древнегреческий философ Сократ отказывается исследовать... Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...
	Тема : Основные понятия математической логики А представляет собой двоичную запись числа 226, столбец значений аргумента в – числа 154, столбец значений аргумента с – числа 75....		Луна: корень землян, врата в Мир Олег Ермаков Все те, кто поистине... Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...
	2. Основы логики и логические основы компьютера Основы логики. Основные... Информационные процессы в живой природе, обществе и технике: получение, передача, преобразование, хранение и использование информации....		Программа по формированию навыков безопасного поведения на дорогах... Основные понятия. Метод математической индукции. Обобщенный метод математической индукции. Геометрическая прогрессия. Треугольные...
	Программа по формированию навыков безопасного поведения на дорогах... Закрепление изученных понятий математической логики: высказывание, тема, рема, истинное высказывание и ложное высказывание		Программа по дисциплине «прикладные протоколы интернет и www» Глобальные вычислительные сети: os unix – основные понятия, Internet – структура и основные понятия, аппаратное обеспечение, программное...

Школьные материалы