Практическая работа специальности 09.02.01.

Практическое занятие № 7

Решение задач по теме: «Булева алгебра предикатов»

Теория

Все логические операции логики высказываний справедливы и для предикатов (отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция). Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. В математической логике приписывание квантора к формуле называется связыванием, а переменную, к которой он относится, называют связанной иначе свободной. Например, в предикате "x A(x, y)Ú"z B(c, z) переменные x и z - связанные, а переменные у и z – свободные.

Чаще всего используют два вида кванторов:

Название	Прочтение	Обозначение
Квантор общности	«все», «всякий», «каждый», «любой»	"
Квантор существования	«существует», «найдется», «хотя бы один»	$

Пусть задан одноместный предикат P(x) на множестве Х = {a₁, a₂, a₃, a₄}, тогда:"xP(x)=P(a₁)&P(a₂)&P(a₃)&P(a₄); $xP(x)=P(a₁)ÚP(a₂)ÚP(a₃)ÚP(a₄).

Говорят, что у квантора всеобщности конъюнктивная природа, а у квантора существования – дизъюнктивная. Квантор уменьшает число свободных переменных в логическом выражении и превращает трёхместный предикат в двухместный, двухместный — в одноместный, одноместный — в высказывание.

Примеры выполнения заданий

1. Пусть предикат Q(x,y) определен на конечных множествах:

X={a₁,a₂,a₃, a₄, a₅}, Y={b₁, b₂, b₃, b₄, b₅, b₆} и имеет таблицу истинности:

X	Y
b₁	b₂	b₃	b₄	b₅	b₆
a₁	И	И	Л	Л	И	Л
a₂	Л	Л	Л	И	И	Л
a₃	И	И	Л	Л	И	И
a₄	Л	И	Л	Л	И	И
a₅	И	И	И	И	И	И

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

Решение. Результат применения кванторов общности и существования по xÎX:

"xQ(x,y)	Y
b₁	b₂	b₃	b₄	b₅	b₆
Л	Л	Л	Л	И	Л
$xQ(x,y)	И	И	И	И	И	И

Результат применения квантора общности по yÎY:

X	"yQ(x,y)
a₁	Л
a₂	Л
a₃	Л
a₄	Л
a₅	И

Результат применения квантора существования по yÎY:

X	$yQ(x,y)
a₁	И
a₂	И
a₃	И
a₄	И
a₅	И

Применив кванторы общности и существования повторно, получим восемь высказываний (0-арных предикатов), представленных в таблице:

Высказывание	Значение истинности
"y"x Q(x, y)	Л
$y"x Q(x ,y)	И
"y$x Q(x ,y)	И
$x"y Q(x ,y)	И
"x$y Q(x ,y)	И
$x$y Q(x ,y)	И

Ход работы

1. Пусть предикат P(x, y) определен на множествах: X={a₁,a₂ a₃,a₄}, Y={b₁,b₂,b₃,b₄,b₅,b₆,b₇,b₈} и имеет таблицу истинности. С помощью кванторов постройте высказывания и определите их истинность:

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	И	Л	И	Л	И	И	Л
a₂	Л	И	И	И	Л	И	И	Л
a₃	И	И	Л	И	Л	Л	Л	Л
a₄	И	И	Л	И	Л	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	Л	Л	И	Л	И	И	Л
a₂	Л	Л	Л	Л	Л	Л	Л	Л
a₃	И	И	Л	И	Л	Л	Л	Л
a₄	Л	Л	Л	И	И	Л	И	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	Л	И	Л	И	Л	И	Л
a₂	Л	И	И	Л	Л	Л	Л	И
a₃	И	Л	Л	Л	Л	Л	Л	И
a₄	Л	И	Л	И	И	Л	Л	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	И	Л	И	И	Л	Л	И
a₂	Л	Л	И	Л	И	И	И	И
a₃	И	Л	И	Л	И	И	Л	И
a₄	И	И	Л	И	Л	Л	Л	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	И	Л	И	Л	И	И	Л
a₂	Л	И	И	И	Л	И	И	Л
a₃	Л	И	Л	И	Л	Л	Л	Л
a₄	И	Л	И	Л	Л	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	И	Л	И	И	Л	Л	Л
a₂	Л	И	И	И	И	Л	Л	И
a₃	И	И	Л	Л	И	И	Л	И
a₄	И	Л	И	Л	И	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	И	Л	И	И	И	И	Л
a₂	Л	И	И	И	И	И	И	Л
a₃	Л	Л	И	И	И	Л	Л	Л
a₄	И	Л	Л	И	И	И	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	Л	Л	И	Л	И	И	Л
a₂	И	И	Л	Л	Л	И	И	Л
a₃	И	И	Л	И	И	И	И	Л
a₄	И	И	Л	Л	И	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	И	Л	И	Л	И	Л	И
a₂	И	Л	Л	И	И	Л	И	Л
a₃	Л	И	Л	И	И	Л	Л	И
a₄	Л	Л	И	И	И	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	Л	Л	Л	Л	Л	Л	Л
a₂	И	И	И	И	Л	И	И	Л
a₃	Л	И	Л	И	И	И	И	И
a₄	Л	Л	Л	И	И	И	Л	И

2. Предикат R(x,y) определен на множествах: X={a₁,a₂,a₃,a₄,a₅}, Y={b₁,b₂,b₃,b₄,b_5,b₆,b₇,b₈} и имеет таблицу истинности. С помощью кванторов постройте высказывания и определите их истинность:

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	Л	Л	Л	Л	И	И	И
a₂	И	И	Л	И	И	И	Л	Л
a₃	И	И	Л	И	И	Л	Л	Л
a₄	Л	Л	Л	И	Л	Л	Л	Л
a₅	Л	Л	Л	Л	Л	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	И	Л	И	Л	И	И	Л
a₂	Л	Л	Л	И	Л	И	Л	Л
a₃	И	И	И	И	Л	И	Л	Л
a₄	Л	Л	И	И	И	И	И	И
a₅	И	Л	Л	И	Л	И	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	Л	И	И	И	И	И	И
a₂	И	Л	Л	И	Л	Л	Л	И
a₃	И	Л	Л	И	Л	Л	Л	И
a₄	И	Л	Л	И	И	Л	Л	И
a₅	И	Л	И	И	И	И	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	И	Л	И	И	Л	Л	И
a₂	Л	Л	И	Л	И	И	И	И
a₃	И	Л	И	Л	И	И	Л	И
a₄	И	И	Л	И	Л	Л	Л	И
a₅	И	Л	И	Л	Л	Л	И	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	И	Л	Л	Л	Л	И	Л
a₂	И	И	И	И	Л	И	И	Л
a₃	И	И	И	И	Л	Л	Л	Л
a₄	И	Л	И	Л	Л	Л	Л	Л
a₅	Л	Л	Л	Л	Л	Л	И	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	Л	Л	И	И	Л	Л	Л
a₂	Л	И	И	Л	И	Л	Л	И
a₃	Л	И	Л	Л	И	И	Л	Л
a₄	И	Л	И	Л	И	Л	Л	Л
a₅	Л	И	Л	И	Л	Л	И	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	И	Л	И	И	И	И	И
a₂	Л	И	И	И	И	И	И	Л
a₃	Л	И	И	И	И	Л	Л	Л
a₄	И	Л	Л	И	И	И	И	И
a₅	И	Л	Л	И	Л	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	Л	Л	И	И	И	И	Л
a₂	И	И	Л	Л	Л	И	И	Л
a₃	И	И	Л	И	И	И	И	Л
a₄	И	И	Л	Л	И	И	Л	Л
a₅	И	И	И	Л	Л	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	И	И	Л	И	И	И	И	И
a₂	И	Л	И	И	И	Л	И	Л
a₃	Л	И	Л	И	И	Л	Л	И
a₄	Л	И	И	И	И	И	Л	Л
a₅	И	Л	Л	Л	Л	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇	b₈
a₁	Л	И	Л	И	Л	Л	Л	Л
a₂	И	И	И	И	И	И	И	И
a₃	Л	И	Л	И	И	И	И	И
a₄	Л	Л	Л	И	И	И	Л	И
a₅	Л	Л	Л	И	Л	Л	Л	Л

3. Предикат А(x,y) определен на множествах: X={a₁,a₂,a₃,a₄,a₅,a₆}, Y={b₁,b₂,b₃,b₄,b₅,b₆,b₇} и задан таблично. С помощью кванторов постройте высказывания и определите их истинность:

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	Л	И	Л	И	Л	И	Л
a₂	Л	И	И	И	Л	И	И
a₃	И	И	Л	И	Л	И	Л
a₄	И	И	Л	И	Л	И	Л
a₅	Л	И	Л	Л	И	И	Л
a₆	И	И	Л	Л	Л	Л	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	Л	И	Л	И	Л	Л	И
a₂	Л	И	И	И	Л	Л	Л
a₃	И	И	Л	И	Л	И	И
a₄	И	И	Л	И	Л	И	Л
a₅	Л	И	Л	И	И	Л	И
a₆	Л	Л	Л	Л	Л	Л	Л

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	Л	И	Л	И	Л	Л	И
a₂	Л	И	И	И	Л	Л	Л
a₃	Л	Л	Л	И	Л	Л	И
a₄	Л	Л	И	И	И	И	И
a₅	Л	И	И	Л	И	И	Л
a₆	Л	И	Л	Л	Л	Л	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	Л	И	Л	И	И	Л	И
a₂	И	И	Л	Л	Л	Л	Л
a₃	И	И	Л	И	Л	Л	И
a₄	Л	И	Л	Л	И	И	И
a₅	И	И	Л	И	И	И	Л
a₆	Л	И	И	И	Л	И	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	И	И	Л	И	Л	И	Л
a₂	Л	И	Л	И	Л	И	Л
a₃	Л	И	Л	И	Л	Л	Л
a₄	Л	Л	Л	Л	Л	И	И
a₅	И	И	Л	И	И	И	Л
a₆	И	Л	И	Л	И	И	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	И	Л	Л	И	Л	И	Л
a₂	Л	Л	Л	И	И	Л	Л
a₃	Л	И	Л	И	И	Л	Л
a₄	Л	Л	Л	Л	И	Л	И
a₅	Л	И	Л	И	И	И	И
a₆	Л	Л	Л	Л	Л	Л	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	Л	И	Л	И	Л	Л	И
a₂	Л	Л	И	Л	Л	Л	Л
a₃	Л	И	Л	И	И	Л	Л
a₄	Л	И	И	Л	Л	Л	И
a₅	Л	Л	Л	И	И	Л	И
a₆	И	И	Л	Л	И	И	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	И	Л	Л	И	Л	И	Л
a₂	Л	Л	Л	И	И	Л	Л
a₃	Л	И	Л	И	И	Л	Л
a₄	Л	Л	Л	Л	И	Л	И
a₅	Л	И	Л	И	И	И	И
a₆	Л	Л	Л	Л	Л	Л	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	И	Л	Л	Л	И	И	И
a₂	И	Л	Л	Л	Л	И	И
a₃	И	Л	И	И	Л	И	И
a₄	И	Л	И	И	Л	И	И
a₅	Л	И	И	И	И	И	И
a₆	Л	И	Л	Л	Л	Л	И

X	Y
b₁	b₂	b₃	b₄	b₅	b₆	b₇
a₁	Л	Л	Л	И	Л	И	И
a₂	Л	И	Л	Л	И	Л	И
a₃	Л	И	Л	Л	Л	И	Л
a₄	И	Л	Л	Л	И	Л	Л
a₅	И	И	Л	Л	И	И	И
a₆	Л	И	Л	Л	Л	Л	И

Практическое занятие № 7 Решение задач по теме: «Булева алгебра предикатов»

Решение. Результат применения кванторов общности и существования по x ÎX: " xQ(x,y)

Л И Л И

И Л И И

X Y b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 a 1

Л Л Л И

Л И И Л

X Y b 1 b 2 b 3 b 4 b 5 b 6 b 7 a 1

Л И Л Л

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

27.11.2022