Рассмотрим некоторые схемы доказательства теорем. - раздел Математика, КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ 1) Пусть ...
1) Пусть и - одноместные предикаты, определённые на множестве . Докажем теорему (1): .
Доказательство можно построить по следующей схеме: выбрать элемент такой, что . Исходя из конкретных условий теоремы, доказывают, что из истинности высказывания вытекает истинность высказывания . Заключают, что импликация принимает значение «истина». Этим фактически заканчивается доказательство теоремы (1). В самом деле, если элемент такой, что , то . Тогда высказывание принимает значение «истина», независимо от истинностного значения высказывания . По определению квантора общности, условие теоремы (1) выполняется для всякого элемента из множества .
2) Схема доказательства, основанная на законе силлогизма:
.
Эта формула является тавтологией. Формула - является логическим следствием формул и .
Иногда для доказательства теоремы (1) находят цепочку импликаций , ,…, . На основании правила цепного заключения делают вывод о справедливости теоремы:.
3) Схема разбора случаев основана на следующей тавтологии:
.
а) Если выполняется , то тоже выполняется.
б) Допускаем, что существует , и выполняется .
в) Если выполняется или , то формула является логическим следствием формул и .
4) Доказательство от противного основано на следующем законе:
.
Эта тавтология используется для доказательства теорем вида . Доказательство осуществляется следующим образом: выбирают элемент такой, что . Допускают, что высказывание . Тогда высказывание . Доказывают, что из истинности следует истинность . Если , то . Получили противоречие. Значит, допущение неверно. Вывод: .
Несложно показать, что логические связки , , , имеют ту же таблицу истинности, что и импликация . Поэтому, иногда доказательство теоремы (1) заменяют доказательством одной из равносильных ей связок. Такой метод доказательства также называют доказательством от противного, т.к. во всех случаях предполагают, что заключение теоремы неверно и выводят отсюда противоречие.
Упражнения для самостоятельной работы.
1. Даны следующие высказывания:
P = «Данное число – целое»,
Q = «Данное число – положительное»,
R = «Данное число – простое»,
S = «Данное число
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются формулы из некоторых
Алгоритм преобразования произвольной формулы в СНДФ.
1) Выразить все логические операции через конъюнкцию, дизъюнкцию и отрицание.
2) Используя дистрибутивные законы, преобразовать формулу так, чтобы все конъюнкции выполнялись раньше дизъюнк
Определения.
В математике принято одной и той же буквой обозначать различные объекты, т. е. под буквой фактически понимается переменная, принимающая значения из некоторого множества. Такие перем
Упражнения для самостоятельной работы.
1. Записать следующие высказывания в виде формул логики предикатов.
1) Всякое натуральное число, делящееся на 12, делится на 2, 4 и
Упражнения для самостоятельной работы.
1.Записать на языке логики предикатов аксиому математической индукции.
2. Записать на языке логики предикатов следующую те
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём сле
Новости и инфо для студентов