Методические указания к практической работе № 1

Определение. В ысказыванием называется повествовательное предложение, о котором имеет смысл говорить, что оно истинно или ложно в данный момент времени.

Определение. Высказывание называют простым (элементарным), если оно рассматривается как некое неделимое целое (аналогично элементу множества). Сложным (составным) называется высказывание, составленное из простых с помощью логических связок.

Определение. Отрицанием высказывания является новое высказывание, истинное только тогда, когда исходное высказывание ложно.

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

Пример.

а – «Степан любит танцевать».

Тогда - «Не верно, что Степан любит танцевать».

Определение. Конъюнкцией двух высказываний является новое высказывание, которое истинно только тогда, когда оба исходных высказывания истинны.

Конъюнкция обозначается или a& b и читается как «a и b», «a, но b», «a, а b».

Пример.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Степан любит танцевать и петь».

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

Дизъюнкция обозначается через и читается как «a или b».

Пример.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Степан любит танцевать или петь».

Определение. Импликацией двух высказываний является новое высказывание, которое ложно только тогда, когда первое истинно, а второе – ложно.

Импликация обозначается a® b и читается как «если a, то b»; «из а следует b». При этом a называется посылкой или условием, b – следствием или заключением.

Пример.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Если Степан любит танцевать, то он любит петь».

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

Эквивалентность обозначается a» b и читается как «a эквивалентно b».

Пример.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Для того, чтобы Степан любил танцевать, необходимо и достаточно, чтобы он любил петь».

Сведем все сказанное выше в единую таблицу и введем в рассмотрение еще три операции: сумма по модулю два, штрих Шеффера, стрелка Пирса.

Таблица 1 – Логические операции

В дальнейшем значению «истина» будем ставить в соответствие 1, а «ложь» - 0. Каждой логической операции ставится в соответствие таблица истинности. Таблица истинности выражает значения истинности высказываний в зависимости от значений элементарных высказываний.

Для рассмотренных выше логических операций таблицы истинности будут иметь вид:

Таблица 2 – Таблицы истинности

a
0	1
1	0

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

Определение. Алфавитом называется любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом в данном алфавите называется произвольная конечная последовательность символов (возможно пустая).

Алфавит логики высказываний содержит следующие символы:

· высказывательные переменные;

· логические символы;

· символы скобок.

Определение. Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:

1) любая высказывательная переменная – формула;

2) если А и В – формулы, то Ø А, А Ù В, АÚ В, А® В, АÅ В, А»В, А ï В, А ¯ В – формулы;

3) только те слова являются формулами, для которых это следует из 1) и 2).

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

Пример.

Представить логическими формулами следующие высказывания:

1. «Сегодня понедельник или вторник».

2. «Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые».

3. «Что в лоб, что по лбу».

Решение.

1. Составное (сложное) высказывание «Сегодня понедельник или вторник» состоит из двух простых:

ü а – «сегодня понедельник»;

ü b – «сегодня вторник».

Высказывания а и b соединены связкой «или» очевидно в разделительном смысле (не допускается одновременное выполнение обоих условий), то есть используется логическая связка «сумма по модулю два». Таким образом, данное высказывание представимо логической формулой: a Å b.

2. Сложное высказывание «Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые» включает два простых высказывания:

ü а – «идет дождь»;

ü b – «крыши мокрые».

В первом предложении «Если идет дождь, то крыши мокрые» высказывания а, b соединены связкой «если …, то…»: а ® b.

Во втором «Дождя нет, а крыши мокрые» союз «а» здесь имеет смысл связки «и» (Ù), и кроме того высказывание а следует взять с отрицанием: .

Остается объединить представленные выше два высказывания:

.

3. Высказывание «Что в лоб, что по лбу», если обозначить:

ü а – «в лоб»,

ü b – «по лбу»,

представимо логической формулой a» b.

Определение. Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при которых эта формула принимает значение 1 (0).

Определение. Формула называется тождественно-истинной, или тавтологией (тождественно-ложной или противоречием), если эта формула принимает значение 1 (0) при всех наборах значений переменных.

Пример.

Составить таблицы истинности для формул:

1. ;

2. .

Решение.

1. Таблица истинности для формулы имеет вид:

2. Таблица истинности для формулы имеет вид:

x	y	z

Варианты заданий

Вариант 1

Задание 1. Разбить высказывание на элементарные и записать в виде формул логики высказываний:

а) «В огороде идет дождь, а в Оренбурге дядька»;

б) «Если неверно, что в огороде идет дождь, то, или в Оренбурге дядька, или в огороде бузина».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим .

Задание 3. Доказать выполнимость формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a)

b)

Вариант 2

Задание 1. Разбить высказывание на элементарные и записать в виде формул логики высказываний:

а) «Функция непрерывна и дифференцируема»;

б) «Если функция не является непрерывной, то она недифференцируема».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим .

Задание 3. Доказать выполнимость формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x → (y ↓ z) и (x → y) ↓ (x → z)

b) ((x ≡ y) · (x | y)) и x & y

Вариант 3

Задание1. Пусть A – высказывание «Завтра экзамен», B – высказывание «Студент пишет шпаргалки». Сформулировать словесно:

; ;

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим .

Задание 3. Доказать выполнимость формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x → (y ≡ z) и (x → y) ≡ (x → z)

b) (x → y) и

Вариант 4

Задание 1. Пусть A – высказывание «Завтра экзамен», B – высказывание «Студент пишет шпаргалки». Сформулировать словесно:

; .

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим .

Задание 3. Доказать тождественную истинность формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x ≡ (y | z) и (x ≡ y) | (x ≡ z)

b) (((x ↓ y)↓ (x ↓ y)) ((x ↓ x))↓ (y ↓ y))) и (x y)

Вариант 5

Задание 1. Какой логической операции соответствует употребление «или» в высказываниях:

а) Родители разрешили завести или собаку, или кошку.

б) Кошелек или жизнь!

в) «Если Иван подготовится к экзамену, то он сдаст экзамен успешно и его мама будет довольна».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим ;

Задание 3. Доказать тождественную истинность формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x ↓ (y | z) и (x ↓ y) | (x ↓ z)

b) (x → z) и ((x (y & z)) → ((x y) & z))

Вариант 6

Задание 1.Записать в виде формул логики высказываний, обозначив за переменные элементарные высказывания:

а) «Если функция не является непрерывной, то она недифференцируема»;

б) «Теорема неверна или в доказательстве допущена ошибка».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Доказать тождественную истинность формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x → (y ↓ z) и (x → y) | (x → z)

b) и

Вариант 7

Задание 1. Записать логическими формулами следующее сложное высказывание:

а) «Либо студент сдает сессию, либо его отчисляют»я;

б) «Если в данном четырехугольнике диагонали имеют равную длину, то этот четырехугольник - ромб».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Доказать тождественную истинность формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x ↓ (y z) и (x ↓ y) (x ↓ z)

b) и

Вариант 8

Задание 1. Записать логическими формулами следующее сложное высказывание:

а) «Завтра будет облачно или будет снег и не будет ветра».

б)«Если платина – драгоценный металл, то все птицы летают».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Доказать тождественную истинность формулы

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x (y z) и (x y) (x z)

b) и

Вариант 9

Задание 1. Записать логическими формулами следующее сложное высказывание:

а)«Неверно, что ветер дует тогда и только тогда, когда идет дождь».

б)«Если Волга впадает в Черное море, то белые медведи живут в Африке».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Доказать тождественную истинность формулы

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x → (y ≡ z) и (x → y) ≡ (x → z)

b) и

Вариант 10

Задание 1. Записать логическими формулами следующее сложное высказывание:

а) «Вася получит пять тогда и только тогда, когда защитит лабораторные работы и успешно сдаст экзамен».

б) «Если погода пасмурная, то идет дождь».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Доказать тождественную истинность формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x → (y | z) и (x → y) | (x → z)

b)

Вариант 11

Задание 1. Пусть A – высказывание «Сегодня холодно», B – высказывание «Студент идет на занятия». Сформулировать словесно:

; ;

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Доказать тождественную истинность формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a) x | (y z) и (x | y) (x | z)

b)

Вариант 12

Задание 1. Пусть A – высказывание «Сегодня холодно», B – высказывание «Студент идет на занятия». Сформулировать словесно:

; .

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Составить таблицы истинности для формулы

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a)

b)

Вариант 13

Задание 1. Записать логическими формулами следующее сложное высказывание:

а) Если студент сдает сессию, то его не отчисляют.

б) Если в данном четырехугольнике стороны имеют равную длину, то этот четырехугольник является ромбом или квадратом».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Составить таблицы истинности для формулы

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a)

b)

Вариант 14

Задание 1. Записать логическими формулами следующее сложное высказывание:

а) «Завтра будет облачно, если будет снег или не будет ветра».

б)«Платина – драгоценный метал или все птицы летают».

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Составить таблицы истинности для формулы

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a)

b)

Вариант 15

Задание 1. Записать логическими формулами следующее сложное высказывание:

а) Если студент сдает все экзамены, то его не отчисляют.

б) В данном треугольнике стороны имеют равную длину тогда и только тогда, когда все углы треугольника равны или он прямоугольный.

Задание 2. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим

Задание 3. Составить таблицы истинности для формулы .

Задание 4. Используя таблицу истинности, установить эквивалентность функций в формулах

a)

b)

Вопросы к защите практической работы № 1

1) Что называется высказыванием? Приведите примеры высказываний.

2)Что такое - таблица истинности? Как обозначаются значения истинности.

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

4) Сформулируйте определение конъюнкции высказываний.

5) Сформулируйте определение дизъюнкции высказываний.

6) Сформулируйте определение импликации высказываний.

7) Сформулируйте определение эквиваленции высказываний.

8) Что называется отрицанием высказывания? Приведите пример.

9) Что называется логической формулой?