Высказывания, логические операции

1 2 3

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Саратовский государственный технический университет

ВЫСКАЗЫВАНИЯ, ЛОГИЧЕСКИЕ ФУНКЦИИ И ПРЕДИКАТЫ

Методические указания

к выполнению лабораторных работ

по курсу “Дискретная математика”

для студентов специальности 220400

всех форм обучения

Электронное издание локального распространения

Одобрено

редакционно-издательским советом

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

технического университета

Саратов 2011

Все права на размножение и распространение

в любой форме остаются за разработчиком.

Нелегальное копирование и использование данного продукта запрещено.

Составители: Терентьев Александр Александрович

Под редакцией В.Б.Байбурина

Рецензент Н.Н.Клеванский

410054, Саратов, ул. Политехническая, 77

Научно-техническая библиотека СГТУ

Тел. 52-63-81, 52-86-01

http://lib.sstu.ru

регистрационный

номер

Саратовский государственный

технический университет 2011

Введение

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

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

Лабораторная работа рассчитана на 6 часов аудиторных занятий и 8 часов самостоятельной работы студентов.

Ниже приводятся основные определения операций и функций. При выполнении лабораторной работы студенты (кроме приведенных сведений) должны руководствоваться материалом лекций по данному курсу и приведенному списку литературы.

Высказывания, логические операции

Высказывание- это такое утверждение, про которое можно сказать истинное оно или ложное. Если высказывание истинно, считаем, что оно принимает значение 1 (логическая единица), если ложно 0 (логический ноль).

Из простых высказываний можно получать более сложное с помощью логических операций.

Введем основные логические операции.

1. Дизъюнкция (логическое сложение, логическое «или»)

– принимает значение «истина», если истинно хотя бы одно из простых высказываний, и значение «ложь», если ложны все высказывания.

2. Конъюнкция (логическое умножение, логическое «и»)

– принимает значение «истина», если истинны все простые высказывания, и значение «ложь», если ложно хотя бы одно простое высказывание.

3. Инверсия (отрицание, логическое «не»)

– принимает значение «истина», если исходное высказывание ложно, и значение «ложь», если исходное высказывание истинно.

4. Импликация (логическое следование)

– принимает значение «ложь», если первое высказывание истинное, а второе ложное и значение «истина» во всех остальных случаях.

5. Эквивалентность (равнозначность, тождественность)

– принимает значение «истина», если исходные высказывания одинаковы, и значение «ложь», если исходные высказывания различные.

6. Неэквивалентность (неравнозначность, исключающее ИЛИ, сумма по модулю 2) – принимает значение «ложь», если исходные высказывания одинаковые, и значение «истина», если исходные высказывания различные.

Обозначения:

1) дизъюнкция А или В, A or B, A۷B, A+B;

2) конъюнкция А и В, A and B, A&B, A^B, AB;

3) инверсия Ā, ┐А,!А;

4) импликация А→В;

5) эквивалентность А ~ В;

6) неэквивалентность ┐(А ~ В), А В, A xor B.

Логические функции

Логическая функция – это функция, принимающая два значения (ложь - истина), аргумента которой тоже принимают два значения (ложь - истина).

Таблица истинности логической функции – это таблица, содержащая все комбинации аргументов и соответствующие им значения функций. Логические функции считаются равными, если их таблицы истинности совпадают.

Выполнимыми функциями называются функции, если существуют аргументы, при которых функция принимает значение «истина». Если функция принимает значение «истина» при всех аргументах, то она называется «тождественно истинной» (общезначимой). Если при всех значениях аргументов функция принимает значение «ложь», то она называется «тождественно ложной» (противоречивой).

Предикаты

Предикатом называется функция, принимающая два значения (ложь-истина), аргументы которой могут принимать произвольные значения. Предикаты можно задавать в виде P =(условие). Если условие выполняется, P = 1 (истина), если не выполняется, P = 0 (ложь). При задании предиката можно использовать логические операции, например, P(x,y) =(x>0) and (y>0).

Кванторы

Кванторы – это логические эквиваленты слов: каждый, некоторый. Будем использовать следующие кванторы:

1) квантор общности P(x) означает, что утверждение Р(x) верно для всех x;

2) квантор существования P(x) означает, что найдется такое значение x, при котором утверждение P(x) верно.

При формировании утверждения, противоположного данному, кванторы меняются на противоположные (квантор общности на квантор существования и наоборот). Также меняются на противоположные сами предикаты (например, «Р(x) – истина» на «Р(x) - ложно», то есть «истина - ┐ Р(x)».

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

	Вариант 1
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!AB+A!B, где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинно только одно простое высказывание.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. ₁₂ Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 2
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!A!B+AB, где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны любые два высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 3
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)= A!B+!AB, где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 4
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)= AB+!A!B, где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда ложны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2}_Æ Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 5
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!(!A!B+AB), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинно только одно простое высказывание.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 6
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!(!AB).!(A!B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны любые два высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 7
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!(AB+!A!B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 8
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!(A!B)^.!(!AB), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда ложны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 9
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)= (A+B)^.!(A^. B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинно только одно простое высказывание.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. ₁₂_Æ Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 10
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!(!AB+A!B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны любые два высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. ₁₂ если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 11
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!(AB)^. (A+B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} Если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 12
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!(A!B+!AB), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда ложны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. ₁ если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 13
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)= (!A+!B)^.(A+B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинно только одно простое высказывание.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 14
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)= (!A+B)(A+!B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны любые два высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. ₁₂_Æ если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 15
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!((!A+B)(A+!B)), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 16
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)= AB+!(A+B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда ложны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 17
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)= (A+B)(!A+!B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинно только одно простое высказывание.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 18
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)= (A+!B)(!A+B), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны любые два высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.
	Вариант 19
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!((A+!B)(!A+B)), где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда истинны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2}_Æ если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии. (и без инверсии)
	Вариант 20
Задание 1. X,y: real; A, B, P: boolean В каких координатных четвертях (1, 2, 3, или 4) предикат P(x,y)=!(A+B)+AB, где A(x)=(x>0), B(y)=(y>0), принимает значение «истина»? Записать наиболее кратким способом (так чтобы переменные встречались один раз) 1. P, выраженное через A и B в символах языка Pascal (можно пользоваться символами OR, AND, XOR, NOT), 2. P, выраженное через x и y в виде P=(условие). Задание 3. Из простых высказываний (A, B и С) построить составное высказывание, которое было бы истинно тогда и только тогда, когда ложны все высказывания.	Задание 2. Определить, справедливы ли утверждения и , если . Сформировать утверждения, противоположные данным и определить, справедливы ли они. Задание 4. Определить, являются ли следующие высказывания тождественно истинными, тождественно ложными или выполнимыми. _{1 2} если высказывание выполнимое, упростить его так, чтобы одна переменная встречалась только один раз и без инверсии.