Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Задачи по математической логике (+примеры решения и комментарии) - файл 1.rtf


Задачи по математической логике (+примеры решения и комментарии)
скачать (5815.9 kb.)

Доступные файлы (1):

1.rtf5816kb.25.11.2011 22:27скачать

содержание
Загрузка...

1.rtf

  1   2   3
Реклама MarketGid:
Загрузка...
Задачи по математической логике
1. Элементы алгебры высказываний

1.1 Логические операции над высказываниями

1.2 Равносильные формулы алгебры высказываний

1.3 Нормальные формы

1.4. Логические следствия

2. Решение задач с помощью алгебры высказываний

2.1 Исследование рассуждений

2.2 Получение логических следствий из данных формул и посылок для данных логических следствий

2.3 Необходимые и достаточные условия

2.4 Анализ и синтез релейно-контактных схем

1. Элементы алгебры высказываний
1.1 Логические операции над высказываниями
Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание X ложно, и ложным, если высказывание X истинно.

Отрицание высказывания X обозначается и читается «не X» или «неверно, что X».

Логические значения высказывания можно описать с помощью таблицы


X



1

0

0

1


Таблицы такого вида принято называть таблицами истинности.

Конъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если оба высказывания X, Y истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний X, Y обозначается символом X&Y или (XÙY), читается «X и Y». Высказывания X и Y называются членами конъюнкции или конъюнктивными элементами.

Логические значения конъюнкции описываются следующей таблицей истинности:



X

Y

X&Y

1

1

1

1

0

0

0

1

0

0

0

0


Например, для высказываний «6 делится на 2», «6 делится на З» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на З», которое, очевидно, истинно.

Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний.

Дизъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если хотя бы одно из высказываний X, Y истинно, и ложным, если они оба ложны.

Дизъюнкция высказываний X, Y обозначается символом XY, читается «X или Y», где «или» используется в неразделительной форме. Высказывания X и Y называются членами дизъюнкции.

Логические значения дизъюнкции описываются следующей таблицей истинности:


X

Y

XY

1

1

1

1

0

1

0

1

1

0

0

0


Например, высказывание «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый».

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

Импликация высказываний X, Y обозначается символом X Y, читается «если X, то Y» или «из X следует Y». Высказывание X называют посылкой, высказывание Y – заключением.

Логические значения операции импликации описываются следующей таблицей истинности:


X

Y

XY

1

1

1

1

0

0

0

1

1

0

0

1


Например, высказывание «Если число 12 делится на 6, то оно делится на З», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».

Употребление слов «если ..., то ...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание X ложно, то высказывание «Если X, то Y» вообще не имеет смысла. Кроме того, строя предложение вида «если X, то Y» в обыденной речи, мы всегда подразумеваем, что предложение Y вытекает из предложения X. Употребление слов «если ..., то ...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.

Эквиваленцией (или эквивалентностью) двух высказываний X, Y называется высказывание, которое считается истинным, когда оба высказывания X, Y либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.

Эквиваленция высказываний X, Y обозначается символом X Y, читается «для того, чтобы X, необходимо и достаточно, чтобы Y» или «X тогда и только тогда, когда Y». Высказывания X, Y называются членами эквиваленции.

Логические значения операции эквиваленции описываются следующей таблицей истинности:


X

Y

XY

1

1

1

1

0

0

0

1

0

0

0

1


Например, эквиваленция «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда P= Q » является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ P= =Q» либо одновременно истинны, либо одновременно ложны.

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

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция «Штрих Шеффера». Эта операция обозначается символом и определяется следующей таблицей истинности:


X

Y



1

1

0

1

0

1

0

1

1

0

0

1


Штрих Шеффера - функция, принимающая значение ложь, если X – истинно и Y – истинно.

Очевидно, имеют место равносильности:

1)

2)

Из этих двух равносильностей следует, что всякая формула алгебры логики может быть заменена равносильной формулой, содержащей только операцию «Штрих Шеффера».

Отметим, что .

Стрелка Пирса (функция Вебба) XY – функция, принимающая значение истина, когда X – ложно и Y – ложно.



X

Y

XY

1

1

0

1

0

0

0

1

0

0

0

1


Отметим, что XY =

Функция сложение по модулю 2 (функция разноименности, или сумма Жегалкина) - функция, принимающая значение истинно, когда X и Y принимают противоположные значения.



X

Y



1

1

0

1

0

1

0

1

1

0

0

0


Отметим, что = .

С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний X, Y, Z можно построить высказывания
(X&Y)Z и X .
Первое из них есть дизъюнкция конъюнкции X, Y и отрицания выказывания Z, а второе высказывание есть импликация, посылкой которой является высказывание X, а заключением - отрицание дизъюнкции высказывания Y и конъюнкции высказываний X, Z.

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

Высказывания обозначаются большими буквами латинского алфавита А, В, С, …

Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Если над формулой стоит знак отрицания, то скобки тоже опускаются.

В связи с этим формулы
(X&Y)Z и X
могут быть записаны так:
X&YZ и X .
Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логическим значением формулы в случае, если X = 1, Y = 1, Z=0 будет истина, то есть = 1.

Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности. Эта таблица будет содержать 2n строк, где n – количество переменных.

Например, для формулы таблица истинности имеет вид:


X

Y











1

1

0

0

1

0

0

1

0

0

1

0

1

1

0

1

1

0

1

0

0

0

0

1

1

1

0

0
  1   2   3



Скачать файл (5815.9 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru