Читайте также:
|
Пример 1. Утверждение “Симпсон будет признан судом виновным тогда и только тогда, когда все 12 присяжных заседателей признают его виновным” может быть записано в виде формулы B≡(A1&A2&...&A12), где B означает виновность, а An - факт признания вины n-ым присяжным заседателем. Равносильная ей формула ךB≡ ך(A1&A2...&A12) по закону де Моргана может быть преобразована в формулу ךB≡(ךA1 V ךA2 &...ךA12), которую можно интерпретировать так: “Симпсон не будет признан судом виновным тогда и только тогда, когда хотя бы один из 12 присяжных заседателем не признает его вины”.
Пример 2. Рассмотрим следующую задачу. Имеется текстовый файл, который необходимо прочитать посимвольно до появления любого из трех символов: (%,#,EOF). Привести возможные варианты решения этой задачи. В первую очередь нас интересует построение условия для циклической конструкции, выполняющей чтение символов из файла. Обозначим факт появления первого символа как А, второго - как В и третьего - как С. Тогда условие, при котором читаются символы из файла будет записано в виде следующей формулы: (ךA)&(ךB)&(ךC) Однако для данной формулы имеется логически эквивалентная ей конструкция: ך(A V B V C) Поэтому можно предложить два варианта реализации цикла чтения содержимого файла на языке программирования С.
9. Законы логики.
Равносильности формул логики высказываний часто называют законами логики. Знание законов логики позволяет проверять правильность рассуждений и доказательств.
Закон тождества. Он сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует. (A = A)
Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. (A&( ך A)) = ”Это яблоко спелое” и ”Это яблоко не спелое”.
Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. ”Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание. (AV(ךA)) =
Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. ”Неверно, что 2x2 не равно 4”. (ך(ךA)) = A
Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых ”сомножителей” равносильна одному из них. (A&A) = A, (AVA) = A
Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
Коммутативность: (A&B) = (B&A), (AVB) = (B VA)
Ассоциативность: (A&B)&C = A&(B&C) (AVB)VC = AV(B VC)
Законы дистрибутивности. В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции:
A&(B VC) = (A&B)V(A&C); AV(B&C) = (AVB)&(AVC)
Законы де Моргана: (ך(A&B)) = ((ךA)V(ךB)) - отрицание логического произведения эквивалентно логической сумме отрицаний множителей; (ך(AVB)) = ((ךA)&(ךB)) - отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.
Законы поглощения A&(A V B) = A; AV(A&B) = A
Законы склеивания (AVB)&((ךA)VB) = B; (A&B)V((ךA)&B) = B
10. Понятие теоремы. Основная теорема логического вывода и ее доказательство.
· Формула G теории L называется теоремой теории L, если существует вывод в L, в котором последней формулой является G. Вообще говоря, может не существовать алгоритма, позволяющего по формуле определить существование ее вывода. Теория, для которой такой алгоритм существует, называется разрешимой, в противном случае – неразрешимой.
Доказать теорему означает построить вывод в данной Формальной Теории.
· Лемма: формула, которая используется в процессе вывода и сама имеет вывод в данной формальной теории.
Построение вывода для заданной формулы является непростой задачей. Ещё более сложной задачей может быть ответ на вопрос: А существует ли данный вывод?
Одной из важнейших задач современной науки является:
1) Построение алгоритмов, определяющих существует доказательство алгоритмов или нет. Если такой алгоритм удается построить для теории, то теория называется разрешимой.
2) Построение методов алгоритмического доказательства теоремы.
Дата добавления: 2015-05-05; просмотров: 147 | Поможем написать вашу работу | Нарушение авторских прав |