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

Скачать 0.75 Mb.

Название	Тема: Основные понятия математической логики
страница	3/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

если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных
если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);
количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 2³=8 строчек, если заданы только 6 из них, то можно найти 2^8-6=2²=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)
логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)

П

X

Y

Z

F

1

0

0

1

0

0

0

1

1

1

1

0

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

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

1) ¬X  ¬Y  ¬Z 2) X  Y  Z 3) X  Y  Z 4) ¬X  ¬Y  ¬Z

Решение (основной вариант):

нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных
если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F
перепишем ответы в других обозначениях:
1) 2) 3) 4)
первое выражение, , равно 1 только при , поэтому это неверный ответ (первая строка таблицы не подходит)
второе выражение, , равно 1 только при , поэтому это неверный ответ (первая и вторая строки таблицы не подходят)
третье выражение,, равно нулю при , поэтому это неверный ответ (вторая строка таблицы не подходит)
наконец, четвертое выражение, равно нулю только тогда, когда , а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности
таким образом, правильный ответ – 4 ; частичная таблица истинности для всех выражений имеет следующий вид:

X	Y	Z	F
1	0	0	1	0 ×	0 ×	1	1
0	0	0	1	–	–	0 ×	1
1	1	1	0	–	–	–	0

(красный крестик показывает, что значение функции не совпадает с F, а знак «–» означает, что вычислять оставшиеся значения не обязательно).

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

серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений с «закорючками», поэтому рекомендуется сначала внимательно перевести их в «удобоваримый» вид;
расчет на то, что ученик перепутает значки  и  (неверный ответ 1)
в некоторых случаях заданные выражения-ответы лучше сначала упростить, особенно если они содержат импликацию или инверсию сложных выражений (как упрощать – см. разбор задачи А8)

Решение (вариант 2):

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

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

метод применим не всегда, то есть, найденная в п. 4 функция может отсутствовать среди ответов

Е

X

Y

Z

F

1

0

0

1

0

0

0

0

1

1

1

0

ще пример задания:

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

1) ¬X  ¬Y  ¬Z 2) X  Y  Z 3) X  ¬Y  ¬Z 4) X  ¬Y  ¬Z

Решение (вариант 2):

перепишем ответы в других обозначениях:
1) 2) 3) 4)
в столбце F есть единственная единица для комбинации , простейшая функция, истинная (только) для этого случая, имеет вид , она есть среди приведенных ответов (ответ 3)
таким образом, правильный ответ – 3.

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

С

X

Y

Z

F

1

1

1

1

1

1

0

1

1

0

1

1

имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  ¬Y  Z 2) X  Y  Z 3) X  Y  ¬Z 4) ¬X  Y  ¬Z

С

X

Y

Z

F

0

1

0

0

1

1

0

1

1

0

1

0

имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  Y  ¬Z 2) X  Y  ¬Z 3) ¬X  ¬Y  Z 4) X  ¬Y  Z

С

X

Y

Z

F

0

0

0

1

0

0

1

0

0

1

0

0

имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  ¬Y  Z 3) X  Y  ¬Z 4) ¬X  ¬Y  ¬Z

С

X

Y

Z

F

0

0

0

1

0

0

1

0

0

1

0

1

имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬X  ¬Y  Z 2) ¬X  ¬Y  Z 3) X  Y  ¬Z 4) X  Y  Z

С

A

B

F

0

0

1

0

1

1

1

0

1

1

1

0

имволом F обозначена логическая функция от двух аргументов (A и B), заданная таблицей истинности. Какое выражение соответствует F?

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

С

X

Y

Z

F

0

0

0

0

1

1

0

1

1

0

0

1

имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  Y  ¬Z 3) X  (Y  Z) 4) (X  Y)  ¬Z

С

X

Y

Z

F

0

0

0

1

0

0

1

1

0

1

0

1

имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) X  Y  Z 3) X  Y  Z 4) ¬X  ¬Y  ¬Z

С

X

Y

Z

F

0

0

0

1

0

0

1

1

0

1

0

1

1
имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) ¬(X  Y)  Z 2) ¬(X  ¬Y)  Z 3) ¬(X  Y)  Z 4) (X  Y)  Z

С

X

Y

Z

F

0

0

0

0

1

0

1

1

0

1

0

1

имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  Y  Z 2) ¬X  Y  ¬Z 3) X  Y  Z 4) X  Y  ¬Z

С

A

B

F

0

0

0

0

1

1

1

0

1

1

1

1

имволом F обозначена логическая функция от двух аргументов (A и B), заданная таблицей истинности. Какое выражение соответствует F?

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

A12 (базовый уровень, время – 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 – структура и основные понятия, аппаратное обеспечение, программное...

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