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

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

x1x2x3x4x5x6x7x8x9x10F
01011101111
10110011101
01010100100

Каким из при­ведённых ниже вы­ра­же­ний может быть F?

 

1)  x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ x8 ∧ ¬x9 ∧ x10

2)  x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ x5 ∨ ¬x6 ∨ x7 ∨ x8 ∨ ¬x9 ∨ x10

3)  ¬x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 ∨ ¬x8 ∨ x9 ∨ ¬x10

4)  ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 ∧ x9 ∧ ¬x10

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

Ре­ше­ние.

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

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

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

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

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

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

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

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