Отношения логической эквивалентности и логического следствия.


Определение. Формулы и называются логически эквивалентными тогда и только тогда, когда формула – тавтология.

 

Замечание. Формула – тавтология, если таблицы истинности формул и совпадают.

 

Пример. По законам де Моргана, логически эквивалентны формулы и , а также формулы и .

 

Теорема. Отношение логической эквивалентности является отношением эквивалентности.

Рефлексивность, симметричность и транзитивность данного отношения следуют из замечания.

 

Справедливы правило подстановки и правило замены.

 

Пусть и – формулы, содержащие букву , и – формулы, полученные из формул и соответственно подстановкой вместо буквы формулы .

 

Правило подстановки.Если формула логически эквивалентна формуле , то формула логически эквивалентна формуле .

 

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

 

Правило замены.Если формулы и логически эквивалентны, то логически эквивалентны и формулы и .

 

Доказательства правил подстановки и замены основано на сравнении таблиц истинности соответствующих формул.

Пример.Известна тавтология (проверьте самостоятельно). По правилу подстановки, формула логически эквивалентна формуле . По правилу замены, примененному к закону двойного отрицания, получаем, что формула логически эквивалентна формуле . Следовательно, по свойству транзитивности, формулы и логически эквивалентны.

 

Определение. Говорят, что формула логически влечет формулу (из формулы логически следует формула ), если формула является тавтологией.

 

Теорема. Отношение логического следствия является отношением предпорядка, то есть рефлексивным и транзитивным отношением.

 

Пример.Формула логически влечет формулу . В самом деле, в примере 1 предыдущего пункта было доказано, что формула является тавтологией.

 

В Содержание.

 

Задачи.

1. Установить, является ли предложение высказыванием, и если является, истинно оно или ложно.

1) Волга впадает в Каспийское море.

2) Студент второго курса.

3) .

4) .

5) Существует человек, который не старше своего отца.

6) .

7) Марс есть спутник Земли.

8) .

9) .

10) Который час?

 

2. Установить, является ли предложение высказыванием, и если является, истинно оно или ложно.

1) .

2) .

3) .

4) .

5) .

6) .

7) .

8) .

9) .

10) .

 

3. Среди следующих высказываний выделить элементарные и составные. В составных высказываниях обозначить элементарные высказывания буквами и записать с помощью логических символов.

1) Число 6 является делителем числа 36.

2) Число 225 делится нацело на 5.

3) Число 225 делится нацело на 5 и не делится на 10.

4) Если 81 делится нацело на 9, то 81 делится на 3.

5) 16 кратно 2.

6) 18 кратно 2 и 3.

7) .

8) Число 39 имеет 2 простых делителя.

9) Двузначное число 19 простое.

10) Корнями уравнения являются числа 2 и 3.

 

4. Пусть обозначает высказывание “Я увлекаюсь горным туризмом”, а обозначает высказывание “Я изучаю программирование”. Дайте словесную формулировку следующих высказываний:

1) ; 2) ; 3) ; 4) ; 5) ; 6) ;

7) ; 8) ; 9) ; 10) .

 

5. Проверить, является ли формула тавтологией, без построения таблицы истинности.

1) . 6) .
2) . 7) .
3) . 8) .
4) . 9) .
5) . 10) .

 

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

1) .

2) .

3) .

4) .

5) .

6) .

7) .

8) .

9) .

10) .

 

7. Доказать, что формулы логически эквивалентны.

1) и .

2) и .

3) и .

4) и .

5) и .

6) и .

7) и .

8) и .

9) и .

10) и .

 

8. Доказать, что первая формула логически влечет вторую формулу.

1) ; .

2) ; .

3) ; .

4) ; .

5) ; .

6) ; .

7) ; .

8) ; .

9) ; .

10) ; .

 

9. Доказать теорему о том, что отношение логической эквивалентности является отношением эквивалентности.

 

10. Доказать теорему о том, что отношение логического следования является отношением предпорядка.

 

В Ответы и указания.

В Содержание.

 



Дата добавления: 2022-02-05; просмотров: 280;


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

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.019 сек.