Студопедия — Пример 4.3.
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Пример 4.3.






А ┐A — тавтология, А & ┐ А — противоречие, А → ┐ А — выполнимая формула, она истинна при А = Л.

Теорема 4.1. Пусть А — некоторая формула. Тогда:

1. Если А — тавтология, то ┐А — противоречие, и наоборот;

2. Если А — противоречие, то ┐A — тавтология, и наоборот;

3. Если А — тавтология, то неверно, что А — противоречие, но не наоборот;

4. Если А — противоречие, то неверно, что А — тавтология, но не наоборот.

Доказательство. Очевидно из определений.

Теорема 4.2. Если формулы А и АВ — тавтологии, то формула В — тавтология.

Доказательство. От противного. Пусть 1(В) = Л. Но 1(А) = И, так как А — тавтология, значит, 1(АВ) = Л, что противоречит предположению о том, что АВ — тавтология.

Можно перечислить наиболее важные тавтологии (А, В, С – произвольные формулы):

1) А®А;

2) А®(В®А);

3) (А®В)®((В®С)®(А®С)) (цепное рассуждение);

4) (А®(В®С))®((А®В)®(А®С));

5) (А&В)®А, (А&В)®В; (4.1)

6) А®(В®(А&В));

7) А®(АÚВ), В®(АÚВ);

8) (┐В ®┐А)®((┐В®А)®В);

9) ((А ®В)®А)®А (закон Пирса).

Немаловажную роль играют логическое следование и логическая эквивалентность формул.

Говорят, что формула В логически следует из формулы А (обозначается А В), если формула В имеет значение И при всех интерпретациях, при которых формула А имеет значение И. Говорят, что формулы А и В логически эквивалентны (обозначается А В, или просто А = В), если они являются логическим следствием друг друга. Логически эквивалентные формулы имеют одинаковые значения при любой интерпретации.

Теорема 4.3. (Р® Q)Û(┐РÚQ).

Доказательство. Для доказательства достаточно проверить, что формулы действительно имеют одинаковые истин­ностные значения при всех интерпретациях.

Р Q PQ ┐Р ┐Р Q
И И И Л И
Л И И И И
И Л Л Л Л
Л Л И И И

Теорема 4.4. Если А, В, С — любые формулы, то имеют место следующие логические эквивалент­ности:

1. A A=A, A & A = A;

2. А В = В А, A &В = B& A;

3. А С) = (А В) С,A &(В&С) = (A &В)&С;

4. A (B&C)=(A B)&(A C), A &(B C) = (A &B) (A &C);

5. (A&B) A=A, (A В)& A = A;

6. A Л = A, A &;Л = Л; (4.2)

7. A И = И, A & И = A;

8. ┐ (┐ A) = A; ┐ (A Ú B) = ┐ A&┐ B;

9. ┐ (A&B) = ┐ A ┐B,

10. A ┐A = И, A & ┐ A = Л

Доказательство всех эквивалентностей (они нам уже знакомы по разделу 3) непосредственно проводится построением таблиц истинности.

Анализируя все полученные результаты, можем, таким образом, заметить, что алгебра {И,JI}; ,&,┐ является булевой алгеброй, которая называется алгеб­рой высказываний.

Теорема 4.5. P1 &... & Pn Q тогда и только тогда, когда (P1 &... & Pn) Q тавтология.

Доказательство. Необходимость. Пусть I(P1 &... & Pn) = И. Тогда

I(Q) = И и I(P1 &... & Pn Q) = И.

Пусть I(P1 &... & Pn) = Л. Тогда I(P1 &... & Pn Q) = И при любой интерпретации I. Таким образом, формула P1 &... & Pn Q общезначима.

Достаточность. Пусть I(P1 &... & Pn) = И. Тогда I(Q) = И, иначе бы формула P1 &... & Pn Q не была бы тавтологией. Таким образом, формула Q — логическое следствие формулы P1 &... & Pn.

Теорема 4.6. P1 &... & Pn Q тогда и только тогда, когда P1 &... & Pn & ┐Q — противоречие.

Доказательство. По предыдущей теореме P1 &... & Pn Q тогда и только тогда, когда формула P1 &... & Pn Q — тавтология. По первой теореме подраздела 4.1.3 формула P1 &... & Pn Q является тавтоло­гией тогда и только тогда, когда формула ┐ (P1 &... & Pn Q) является противоречием. Имеем:

(P1 &... & Pn Q) = ┐((P1 &... & Pn) Ú Q)=

= ┐┐(P1 &... & Pn) & ┐Q)=P1 &... & Pn & ┐Q.

Определим преобразование логических фигур с помощью подстановки.

Пусть А — некоторая формула, в которую входит переменная х (обозначается А (... х...)) или неко­торая подформула В (обозначается A (… В...)), и пусть С — некоторая формула. Тогда

А (...х...){ С / / х }

обозначает формулу, полученную из формулы А подстановкой формулы С вместо всех вхождений переменной х, а А (... B...){ С / B } обозначает формулу, полученную из формулы А подстановкой формулы С вместо некоторых (в частности, вместо одного) вхождений подформулы В.

Теорема 4.7. Если А(... х...) — тавтология и В — любая формула, то А(...х...){В//х} — тав­тология.

Доказательство. Пусть С = A (... х...){В // х}. Пусть I — интерпретация С (она не содержит x). Пусть . Тогда , но = И, следовательно I(C) = И.

Теорема 4.8. Если А (... В...) и В = С, a D = А (... В...){ С/В }, то А=D.

Доказательство. Пусть I — любая интерпретация. Тогда I (В) = I (С), значит I (A) = I (D).







Дата добавления: 2015-10-15; просмотров: 493. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Измерение следующих дефектов: ползун, выщербина, неравномерный прокат, равномерный прокат, кольцевая выработка, откол обода колеса, тонкий гребень, протёртость средней части оси Величину проката определяют с помощью вертикального движка 2 сухаря 3 шаблона 1 по кругу катания...

Неисправности автосцепки, с которыми запрещается постановка вагонов в поезд. Причины саморасцепов ЗАПРЕЩАЕТСЯ: постановка в поезда и следование в них вагонов, у которых автосцепное устройство имеет хотя бы одну из следующих неисправностей: - трещину в корпусе автосцепки, излом деталей механизма...

Понятие метода в психологии. Классификация методов психологии и их характеристика Метод – это путь, способ познания, посредством которого познается предмет науки (С...

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

Машины и механизмы для нарезки овощей В зависимости от назначения овощерезательные машины подразделяются на две группы: машины для нарезки сырых и вареных овощей...

Классификация и основные элементы конструкций теплового оборудования Многообразие способов тепловой обработки продуктов предопределяет широкую номенклатуру тепловых аппаратов...

Studopedia.info - Студопедия - 2014-2024 год . (0.012 сек.) русская версия | украинская версия