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

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

x1x2x3x4x5x6x7F
01011100
11010101
01011010

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

 

1)  (х1 ∨ х2) ∧ ¬хЗ ∧ х4 ∧ ¬х5 ∧ хб ∧ ¬х7

2)  (х1 ∧ х2) ∨ ¬хЗ ∨ х4 ∨ ¬х5 ∨ хб ∨ ¬х7

3)  (х1 ∧ ¬х2) ∨ хЗ ∨ ¬х4 ∨ ¬х5 ∨ хб ∨ ¬х7

4)  (¬х1 ∨ ¬х2) ∧ хЗ ∧ ¬х4 ∧ х5 ∧ ¬хб ∧ х7

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

Ре­ше­ние.

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

 

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

 

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

 

Ва­ри­ант 1 (конъ­юнк­ция (х1 ∨ х2), ¬x3, x4, ¬x5, x6, ¬x7):

 

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

 

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

 

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

 

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