Экзамен. 2. Как получить скнф, используя двойственность

• Название: 2. Как получить скнф, используя двойственность
• Дата: 20.11.2020
• Размер: 0.53 Mb.
• Имя файла: Экзамен.pdf
• Тип: Документы; #152218

БИЛЕТ № 1
1. Дайте определение формулы алгебры высказываний. Приведите примеры различных формул. Классификация формул алгебры высказываний.
2. Как получить СКНФ, используя двойственность?
3. Минимизировать булеву функцию методом Квайна Мак-Класки:


xy
z
y
z
y
x
f



4. Представить булеву функцию в виде многочлена Жегалкина и определить его степень:




xy
x
y
x
f




5. Проверить, справедливо ли следующее логическое следование:


R
Q
P


╞


R
Q
P


БИЛЕТ № 2
1. Равносильные преобразования логических формул высказываний.
2.
Что такое монотонная булева функция и как это связано с дизъюнкцией и конъюнкцией?
3. Проверить на полноту систему булевых функций:




xy
y
x
x





,
1 4. Минимизировать булеву функцию и построить её РКС:
)
(
)
(
y
z
x
z
y
x



5. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: A={a,b,c}, заменить на с каждый символ в слове P.
Начальная и конечная конфигурации стандартны.

БИЛЕТ № 3
1. Понятие выказывания, приведите примеры высказываний. Логические операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Приведите таблицы истинности этих операций.
2. Каковы основные шаги преобразования формулы в СДНФ?
3. Минимизировать булеву функцию методом Карно:


y
x
y
z
x
f



4. Определить принадлежность функции к классу M (монотонных функций):




xy
x
y
x
f




5.
Привести формулу


))
,
(
)
,
(
(
)
(
3 2
3 3
1 2
3 1
1 2
1
x
x
P
x
x
P
x
x
P
x
x
F






к предваренной нормальной форме.
БИЛЕТ № 4
1. Равносильные преобразования логических формул высказываний.
2.
Что такое монотонная булева функция и как это связано с дизъюнкцией и конъюнкцией?
3. Определите, является ли один из следующих предикатов, заданных на множестве действительных чисел, следствием другого:
2
x
y

,
4
x
y

4. Построить РКС булевой функции:



y
x
y
x
y
x
f



)
,
(
5. Определить принадлежность функции к классу S (самодвойственных функций):

 

z
x
y
x
z
y
x
f




)
,
,
(

БИЛЕТ № 5
1. Что такое двойственная булева функция, самодвойственная булева функция, закон двойственности?
2. В чём состоит теорема Поста? Как практически применить теорему Поста?
3. Определить принадлежность функции к классу L (линейных функций):



y
x
y
x
y
x
f



)
,
(
4. Изобразите на координатной плоскости множества истинностиследующего двухместного предиката, заданного на множестве действительных чисел R:
y
x


3 2
5.
Проверить на полноту систему булевых функций:




xy
y
x
x




,
БИЛЕТ № 6
1. Предваренная нормальная форма алгебры предикатов.
2. Понятие о машине Тьюринга. Ее структура и способ функционирования.
3. Составьте отрицание к фразе: в каждой группе есть студент, который каждый день опаздывает на занятия. Записать фразу и её отрицание предикатной формулой.
4. Минимизировать булеву функцию

 

y
x
y
x
y
x
f




)
,
(
5. Определить принадлежность функции к классу L (линейных функций):

 

z
x
y
x
z
y
x
f




)
,
,
(

БИЛЕТ № 7
1. В чем состоит минимизация булевых функций методом Квайна – Мак-
Класки?
2. Операции над предикатами (логические операции, кванторы).
3. Проверить на полноту систему булевых функций:




xy
y
x
x





,
0 4. Минимизировать булеву функцию методом Квайна Мак-Класки:


1101
,
1011
,
0111
,
0101
,
0100
,
0010

f
5.
Проверить, справедливо ли следующее логическое следование:


R
Q
P


╞

 

R
P
Q
P



БИЛЕТ № 8
1. Как получить СКНФ, используя таблицу истинности?
2. В чем состоит минимизация булевых функций методом склеивания и применения сокращающих логических тождеств?
3. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: А={a,b,c}. Если Р – непустое слово, то за его первым символом вставить символ с. Начальная и конечная конфигурации стандартны.
4. Определить принадлежность функции к классу S (самодвойственных функций):




z
x
y
x
z
y
x
f




)
,
,
(
5. Минимизировать булеву функцию методом карт Карно:



 

x
y
y
z
x
x
f






БИЛЕТ № 9
1. Что такое линейная функция, функция, сохраняющая ноль и функция, сохраняющая единицу?
2. Логическое следование. Два свойства логического следования. Логическое следование и равносильность формул.
3. Определить принадлежность функции к классу M (монотонных функций):



y
x
y
x
y
x
f



)
,
(
4. Определите, является ли один из следующих предикатов, заданных на множестве действительных чисел, следствием другого:
1 2
2


x
y
,
9 2
2


y
x
5.
Составив таблицу истинности, проверьте, является ли следующая формула тавтологией:






P
Q
P
Q
P




БИЛЕТ № 10
1. Что называется ЭК, ДНФ, правильной ЭК, полной ЭК, СДНФ?
2.
Что такое тавтология? Приведите основные тавтологии алгебры высказываний.
3. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: А={a,b,c}. Если Р – непустое слово, то за его первым символом вставить символ с. Начальная и конечная конфигурации стандартны.
4.Найти многочлен
Жегалкина следующей булевой функции:




z
x
y
x
z
y
x
f




)
,
,
(
5.
Привести формулу


))
,
(
)
,
(
(
)
(
3 2
3 3
1 2
3 1
1 2
1
x
x
P
x
x
P
x
x
P
x
x
F






к предваренной нормальной форме и сколемовской стандартной форме

БИЛЕТ № 11
1. Дайте определение формулы алгебры высказываний. Приведите примеры различных формул. Классификация формул алгебры высказываний.
2. Как получить СКНФ, используя двойственность?
3. Минимизировать булеву функцию методом Квайна Мак-Класки:


xy
z
y
z
y
x
f



4. Представить булеву функцию в виде многочлена Жегалкина и определить его степень:




xy
x
y
x
f




5. Проверить, справедливо ли следующее логическое следование:


R
Q
P


╞


R
Q
P


БИЛЕТ № 12
1. Равносильные преобразования логических формул высказываний.
2.
Что такое монотонная булева функция и как это связано с дизъюнкцией и конъюнкцией?
3. Проверить на полноту систему булевых функций:




xy
y
x
x





,
1 4. Минимизировать булеву функцию и построить её РКС:
)
(
)
(
y
z
x
z
y
x



5. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: A={a,b,c}, заменить на с каждый символ в слове P.
Начальная и конечная конфигурации стандартны.

БИЛЕТ № 13
1. Понятие выказывания, приведите примеры высказываний. Логические операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Приведите таблицы истинности этих операций.
2. Каковы основные шаги преобразования формулы в СДНФ?
3. Минимизировать булеву функцию методом Карно:


y
x
y
z
x
f



4. Определить принадлежность функции к классу M (монотонных функций):




xy
x
y
x
f




5.
Привести формулу


))
,
(
)
,
(
(
)
(
3 2
3 3
1 2
3 1
1 2
1
x
x
P
x
x
P
x
x
P
x
x
F






к предваренной нормальной форме.
БИЛЕТ № 14
1. Равносильные преобразования логических формул высказываний.
2.
Что такое монотонная булева функция и как это связано с дизъюнкцией и конъюнкцией?
3. Определите, является ли один из следующих предикатов, заданных на множестве действительных чисел, следствием другого:
2
x
y

,
4
x
y

4. Построить РКС булевой функции:



y
x
y
x
y
x
f



)
,
(
5. Определить принадлежность функции к классу S (самодвойственных функций):

 

z
x
y
x
z
y
x
f




)
,
,
(

БИЛЕТ №15
1. Что такое двойственная булева функция, самодвойственная булева функция, закон двойственности?
2. В чём состоит теорема Поста? Как практически применить теорему Поста?
3. Определить принадлежность функции к классу L (линейных функций):



y
x
y
x
y
x
f



)
,
(
4. Изобразите на координатной плоскости множества истинностиследующего двухместного предиката, заданного на множестве действительных чисел R:
y
x


3 2
5.
Проверить на полноту систему булевых функций:




xy
y
x
x




,
БИЛЕТ № 16
1. Предваренная нормальная форма алгебры предикатов.
2. Понятие о машине Тьюринга. Ее структура и способ функционирования.
3. Составьте отрицание к фразе: в каждой группе есть студент, который каждый день опаздывает на занятия. Записать фразу и её отрицание предикатной формулой.
4. Минимизировать булеву функцию

 

y
x
y
x
y
x
f




)
,
(
5. Определить принадлежность функции к классу L (линейных функций):

 

z
x
y
x
z
y
x
f




)
,
,
(

БИЛЕТ № 17
1. В чем состоит минимизация булевых функций методом Квайна – Мак-
Класки?
2. Операции над предикатами (логические операции, кванторы).
3. Проверить на полноту систему булевых функций:




xy
y
x
x





,
0 4. Минимизировать булеву функцию методом Квайна Мак-Класки:


1101
,
1011
,
0111
,
0101
,
0100
,
0010

f
5.
Проверить, справедливо ли следующее логическое следование:


R
Q
P


╞

 

R
P
Q
P



БИЛЕТ № 18
1. Как получить СКНФ, используя таблицу истинности?
2. В чем состоит минимизация булевых функций методом склеивания и применения сокращающих логических тождеств?
3. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: А={a,b,c}. Если Р – непустое слово, то за его первым символом вставить символ с. Начальная и конечная конфигурации стандартны.
4. Определить принадлежность функции к классу S (самодвойственных функций):




z
x
y
x
z
y
x
f




)
,
,
(
5. Минимизировать булеву функцию методом карт Карно:



 

x
y
y
z
x
x
f






БИЛЕТ № 19
1. Что такое линейная функция, функция, сохраняющая ноль и функция, сохраняющая единицу?
2. Логическое следование. Два свойства логического следования. Логическое следование и равносильность формул.
3. Определить принадлежность функции к классу M (монотонных функций):



y
x
y
x
y
x
f



)
,
(
4. Определите, является ли один из следующих предикатов, заданных на множестве действительных чисел, следствием другого:
1 2
2


x
y
,
9 2
2


y
x
5.
Составив таблицу истинности, проверьте, является ли следующая формула тавтологией:






P
Q
P
Q
P




БИЛЕТ № 20
1. Что называется ЭК, ДНФ, правильной ЭК, полной ЭК, СДНФ?
2.
Что такое тавтология? Приведите основные тавтологии алгебры высказываний.
3. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: А={a,b,c}. Если Р – непустое слово, то за его первым символом вставить символ с. Начальная и конечная конфигурации стандартны.
4.Найти многочлен
Жегалкина следующей булевой функции:




z
x
y
x
z
y
x
f




)
,
,
(
5.
Привести формулу


))
,
(
)
,
(
(
)
(
3 2
3 3
1 2
3 1
1 2
1
x
x
P
x
x
P
x
x
P
x
x
F






к предваренной нормальной форме и сколемовской стандартной форме

БИЛЕТ № 21
1. Дайте определение формулы алгебры высказываний. Приведите примеры различных формул. Классификация формул алгебры высказываний.
2. Как получить СКНФ, используя двойственность?
3. Минимизировать булеву функцию методом Квайна Мак-Класки:


xy
z
y
z
y
x
f



4. Представить булеву функцию в виде многочлена Жегалкина и определить его степень:




xy
x
y
x
f




5. Проверить, справедливо ли следующее логическое следование:


R
Q
P


╞


R
Q
P


БИЛЕТ № 22
1. Равносильные преобразования логических формул высказываний.
2.
Что такое монотонная булева функция и как это связано с дизъюнкцией и конъюнкцией?
3. Проверить на полноту систему булевых функций:




xy
y
x
x





,
1 4. Минимизировать булеву функцию и построить её РКС:
)
(
)
(
y
z
x
z
y
x



5. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: A={a,b,c}, заменить на с каждый символ в слове P.
Начальная и конечная конфигурации стандартны.

БИЛЕТ № 23
1. Понятие выказывания, приведите примеры высказываний. Логические операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Приведите таблицы истинности этих операций.
2. Каковы основные шаги преобразования формулы в СДНФ?
3. Минимизировать булеву функцию методом Карно:


y
x
y
z
x
f



4. Определить принадлежность функции к классу M (монотонных функций):




xy
x
y
x
f




5.
Привести формулу


))
,
(
)
,
(
(
)
(
3 2
3 3
1 2
3 1
1 2
1
x
x
P
x
x
P
x
x
P
x
x
F






к предваренной нормальной форме.
БИЛЕТ № 24
1. Равносильные преобразования логических формул высказываний.
2.
Что такое монотонная булева функция и как это связано с дизъюнкцией и конъюнкцией?
3. Определите, является ли один из следующих предикатов, заданных на множестве действительных чисел, следствием другого:
2
x
y

,
4
x
y

4. Построить РКС булевой функции:



y
x
y
x
y
x
f



)
,
(
5. Определить принадлежность функции к классу S (самодвойственных функций):

 

z
x
y
x
z
y
x
f




)
,
,
(

БИЛЕТ № 25
1. Что такое двойственная булева функция, самодвойственная булева функция, закон двойственности?
2. В чём состоит теорема Поста? Как практически применить теорему Поста?
3. Определить принадлежность функции к классу L (линейных функций):



y
x
y
x
y
x
f



)
,
(
4. Изобразите на координатной плоскости множества истинностиследующего двухместного предиката, заданного на множестве действительных чисел R:
y
x


3 2
5.
Проверить на полноту систему булевых функций:




xy
y
x
x




,
БИЛЕТ № 26
1. Предваренная нормальная форма алгебры предикатов.
2. Понятие о машине Тьюринга. Ее структура и способ функционирования.
3. Составьте отрицание к фразе: в каждой группе есть студент, который каждый день опаздывает на занятия. Записать фразу и её отрицание предикатной формулой.
4. Минимизировать булеву функцию

 

y
x
y
x
y
x
f




)
,
(
5. Определить принадлежность функции к классу L (линейных функций):

 

z
x
y
x
z
y
x
f




)
,
,
(

БИЛЕТ № 27
1. В чем состоит минимизация булевых функций методом Квайна – Мак-
Класки?
2. Операции над предикатами (логические операции, кванторы).
3. Проверить на полноту систему булевых функций:




xy
y
x
x





,
0 4. Минимизировать булеву функцию методом Квайна Мак-Класки:


1101
,
1011
,
0111
,
0101
,
0100
,
0010

f
5.
Проверить, справедливо ли следующее логическое следование:


R
Q
P


╞

 

R
P
Q
P



БИЛЕТ № 28
1. Как получить СКНФ, используя таблицу истинности?
2. В чем состоит минимизация булевых функций методом склеивания и применения сокращающих логических тождеств?
3. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: А={a,b,c}. Если Р – непустое слово, то за его первым символом вставить символ с. Начальная и конечная конфигурации стандартны.
4. Определить принадлежность функции к классу S (самодвойственных функций):




z
x
y
x
z
y
x
f




)
,
,
(
5. Минимизировать булеву функцию методом карт Карно:



 

x
y
y
z
x
x
f






БИЛЕТ № 29
1. Что такое линейная функция, функция, сохраняющая ноль и функция, сохраняющая единицу?
2. Логическое следование. Два свойства логического следования. Логическое следование и равносильность формул.
3. Определить принадлежность функции к классу M (монотонных функций):



y
x
y
x
y
x
f



)
,
(
4. Определите, является ли один из следующих предикатов, заданных на множестве действительных чисел, следствием другого:
1 2
2


x
y
,
9 2
2


y
x
5.
Составив таблицу истинности, проверьте, является ли следующая формула тавтологией:






P
Q
P
Q
P




БИЛЕТ № 30
1. Что называется ЭК, ДНФ, правильной ЭК, полной ЭК, СДНФ?
2.
Что такое тавтология? Приведите основные тавтологии алгебры высказываний.
3. Описать функциональной таблицей работу машины Тьюринга, реализующую следующий алгоритм: А={a,b,c}. Если Р – непустое слово, то за его первым символом вставить символ с. Начальная и конечная конфигурации стандартны.
4.Найти многочлен
Жегалкина следующей булевой функции:




z
x
y
x
z
y
x
f




)
,
,
(
5.
Привести формулу


))
,
(
)
,
(
(
)
(
3 2
3 3
1 2
3 1
1 2
1
x
x
P
x
x
P
x
x
P
x
x
F






к предваренной нормальной форме и сколемовской стандартной форме