Задания
Версия для печати и копирования в MS Word
Тип Д12 № 4833
i

Дан фраг­мент таб­ли­цы ис­тин­но­сти вы­ра­же­ния F:

x1x2x3x4x5x6x7F
01011101
10110011
01010100

Каким вы­ра­же­ни­ем может быть F?

 

1)  x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7

2)  x1 ∨ ¬x2 ∨ x3 ∨¬x4 ∨ x5 ∨ ¬x6 ∨ x7

3)  ¬x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7

4)  ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7

Спрятать решение

Ре­ше­ние.

Про­ана­ли­зи­ру­ем ва­ри­ан­ты от­ве­тов. Они пред­став­ля­ют собой либо конъ­юнк­цию, либо дизъ­юнк­цию дан­ных семи пе­ре­мен­ных или про­ти­во­по­лож­ных к ним (если x1  — пе­ре­мен­ная, то про­ти­во­по­лож­ная к ней  — это ¬x1).

 

Сна­ча­ла вы­яс­ним, яв­ля­ет­ся F конъ­юнк­ци­ей или дизъ­юнк­ци­ей.

 

Ка­ко­вы бы ни были ло­ги­че­ские пе­ре­мен­ные х1, х2, ... х7 и от­ри­ца­ния к ним, их конъ­юнк­ция может быть равна 1 толь­ко в одном слу­чае  — когда все они равны 1. Из таб­ли­цы ис­тин­но­сти сле­ду­ет, что функ­ция F при­ни­ма­ет зна­че­ние 1 для двух раз­лич­ных на­бо­ров пе­ре­мен­ных и их от­ри­ца­ний, по­это­му F не может быть конъ­юнк­ци­ей. тем самым, от­ве­ты 1 и 4 не под­хо­дят.

 

По­сле­до­ва­тель­но под­ста­вим 2 и 3 ва­ри­ан­ты от­ве­та.

 

Ва­ри­ант 2 (дизъ­юнк­ция x1, x3, x5, x7, ¬x2, ¬x4, ¬x6):

 

В пер­вой стро­ке дан­ной таб­ли­цы зна­че­ние F равно 1. Это зна­чит, что хотя бы одна пе­ре­мен­ная из x1, x3, x5, x7, ¬x2, ¬x4, ¬x6 долж­на быть равна 1, и такая есть  — это х5. Зна­чит, по пер­вой стро­ке ва­ри­ант 2 удо­вле­тво­ря­ет функ­ции F.

 

Во вто­рой стро­ке дан­ной таб­ли­цы зна­че­ние F равно 1. Это зна­чит, что хотя бы одна пе­ре­мен­ная из x1, x3, x5, x7, ¬x2, ¬x4, ¬x6 долж­на быть равна 1, и такая есть  — это, на­при­мер, х6. Зна­чит, по вто­рой стро­ке ва­ри­ант 2 удо­вле­тво­ря­ет функ­ции F.

 

В тре­тьей стро­ке дан­ной таб­ли­цы зна­че­ние F равно 0. Это зна­чит, что все пе­ре­мен­ные x1, x3, x5, x7, ¬x2, ¬x4, ¬x6 долж­на быть равны 0. Так как в тре­тьей стро­ке пе­ре­мен­ные, около ко­то­рых в ва­ри­ан­те 2 стоит от­ри­ца­ние, равны 1, а пе­ре­мен­ные без от­ри­ца­ния равны 0, то по тре­тьей стро­ке ва­ри­ант 2 удо­вле­тво­ря­ет функ­ции F.

 

Ва­ри­ант 2 удо­вле­тво­ря­ет функ­ции F по всем стро­кам таб­ли­цы.

 

Пра­виль­ный ответ  — 2.