Языки и исчисления

Упражнение 1:

Номер 1

Если A и B - пропозициональные формулы, то такой же формулой будет:

Ответ:

(1) ¬A

(2) A¬B

(3) A¬∨¬B

Номер 2

Если A и B - пропозициональные формулы, то такой же формулой будет:

Ответ:

(1) A∧B

(2) AB∨¬B

(3) ¬A∧¬B¬∨A

Номер 3

Если A и B - пропозициональные формулы, то такой же формулой будет:

Ответ:

(1) A∨B

(2) A∨B¬A

(3) A→B¬A

Упражнение 2:

Номер 1

Формулы A и B эквивалентны тогда и только тогда, когда тавтологией является формула:

Ответ:

(1) (A→B)∧(B→A)

(2) (A→B)∨(B→A)

(3) (A→B)∧(¬A→¬B)

Номер 2

Тавтологией является формула (A,B - формулы):

Ответ:

(1) (A∧B)→(B∧A)

(2) (A∨B)→(A∧B)

(3) (A∧B)→(A∨B)

Номер 3

Тавтологией является формула (A,B - формулы):

Ответ:

(1) ¬(A∧B)↔(A∨B)

(2) ¬(A∧B)↔(¬A∨¬B)

(3) ¬(A∧B)↔(A∧B)

Упражнение 3:

Номер 1

Тавтологией является формула (A,B - формулы):

Ответ:

(1) ¬(A∨B)↔(A∧¬B)

(2) ¬(A∨B)↔(A∧B)

(3) ¬(A∨B)↔(¬A∧¬B)

Номер 2

Тавтологией является формула (A,B - формулы):

Ответ:

(1) (A∨(A∧B))↔B

(2) (A∨(A∧B))↔A

(3) (A∨(A∧B))↔A∧B

Номер 3

Тавтологией является формула (A, B - формулы):

Ответ:

(1) (A∧(A∨B))↔B

(2) (A∧(A∨B))↔A

(3) (A∧(A∨B))↔A∨B

Упражнение 4:

Номер 1

Верно утверждение для любой булевой функции  от  аргументов:

Ответ:

(1)

- записывается в виде пропозициональной формулы

(2)

- тавтология, или math

- неопределенна

(3)

и все получаемые из нее формулы - тавтологии

Номер 2

Верно утверждение для произвольных литералов, конъюнктов и дизъюнктов:

Ответ:

(1) дизъюнктивная нормальная форма - дизъюнкция литералов

(2) дизъюнктивная нормальная форма - дизъюнкция конъюнктов

(3) дизъюнктивная нормальная форма - конъюнкция дизъюнктов

Номер 3

Верно утверждение для произвольных литералов, конъюнктов и дизъюнктов:

Ответ:

(1) конъюнктивная нормальная форма - конъюнкция литералов

(2) конъюнктивная нормальная форма - конъюнкция дизъюнктов

(3) конъюнктивная нормальная форма - дизъюнкция конъюнктов

Упражнение 5:

Номер 1

Верна теорема для любой булевой функции :

Ответ:

(1)

- представима дизъюнктивно нормальной формой

(2)

- не представима дизъюнктивно нормальной формой

(3)

- представима только дизъюнктивной нормальной формой

Номер 2

Верна теорема для любой булевой функции :

Ответ:

(1)

- представима конъюнктивно нормальной формой

(2)

- не представима конъюнктивно нормальной формой

(3)

- представима только конъюнктивной нормальной формой

Номер 3

Верна теорема для любой булевой функции :

Ответ:

(1)

- однозначно представима полиномом Жегалкина

(2)

- представима полиномом Жегалкина неоднозначно

(3)

- не представима полиномом Жегалкина

Упражнение 6:

Номер 1

Функция  эквивалентна:

Ответ:

(1)

(2)

(3)

Номер 2

Функция  эквивалентна:

Ответ:

(1)

(2)

(3)

Номер 3

Функция  эквивалентна:

Ответ:

(1)

(2)

(3)

Упражнение 7:

Номер 1

В списке выражений: 2-2=0, 2+3=6, 3+12, 2+2>2+2, 2-0=3-0, 56=50+6 приведено всего истинных и ложных высказываний соответственно:

Ответ:

(1) 2,3

(2) 3,2

(3) 3,3

Номер 3

Отметьте высказывание, которое является выражением:

Ответ:

(1) "климат теплый"

(2) "климат местами теплый, местами - холодный"

(3) "1+2=4"

Языки и исчисления - тест 1