Задание 2. Задачи для самостоятельного решения с ответами

2.1         2.2         2.3         2.4         2.5         2.6         2.7

 

2.1

Дано логическое выражение, зависящее от 5 логических переменных:

x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5

Сколько существует  различных наборов значений переменных, при которых

выражение истинно?

1)    1

2)    2

3)    31

4)    32

Правильный ответ: 1

Пояснение. Приведенное выражение – конъюнкция. Конъюнкция истинна только, если истинны все ее члены. В задаче  все члены – переменные или их отрицания. Т.е. для каждой переменной есть ровно одно допустимое значение:

x1 должно быть истинно, т.е. x1 = 1

¬x2 должно быть истинно, т.е. x2 = 0

x3 должно быть истинно, т.е. x3 = 1

¬x4 должно быть истинно, т.е. x4 = 0

x5 должно быть истинно, т.е. x5 = 1

Таким образом, существует только один набор значений переменных, при которых формула истинна:  <1, 0, 1, 0, 1>

 

2.2

Дано логическое выражение, зависящее от 6 логических переменных:

¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6

Сколько существует  различных наборов значений переменных, при которых

выражение ложно?

1)    63

2)    61

3)    3

4)    1

Правильный ответ: 4

 

Пояснение. Приведенное выражение – дизъюнкция. Дизъюнкция ложна только, если ложны все ее члены. В задаче  все члены – переменные или их отрицания. Поэтому для каждой переменной есть ровно одно допустимое значение:

 

¬x1 должно быть ложно, т.е. x1 = 1

x2 должно быть ложно, т.е. x2 = 0

¬x3 должно быть ложно, т.е. x3 = 1

x4 должно быть ложно, т.е. x4 = 0

¬x5 должно быть ложно, т.е. x5 = 1

¬x6 должно быть ложно, т.е. x6 = 1

Таким образом, существует только один набор значений переменных, при которых формула ложна:  <1, 0, 1, 0, 1, 1>

 

2.3

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

x1	x2	x3	x4	x5	x6	x7	F
0	1	0	1	1	1	0	0
1	0	1	0	1	1	0	1
0	1	0	1	1	0	1	1

Каким выражением может быть 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

Правильный ответ: 4

 

2.4

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

x1	x2	x3	x4	x5	x6	x7	F
0	0	0	1	1	1	0	0
1	0	1	0	1	1	0	1
0	1	0	1	1	0	1	1

Каким выражением может быть 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

Правильный ответ: 2

 

2.5

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

x1	x2	x3	x4	x5	x6	x7	F
0	0	0	1	1	1	0	0
1	0	1	0	1	1	0	1
0	1	0	1	1	0	1	0

Каким выражением может быть 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

Правильный ответ: 3

 

2.6

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

x1	x2	x3	x4	x5	x6	x7	F
0	0	0	1	1	1	0	0
1	0	1	0	1	1	0	0
0	1	0	1	1	0	1	1

Каким выражением может быть 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

Правильный ответ: 1

 

2.7

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

x1	x2	x3	x4	x5	x6	F
1	1	0	0	0	1	0
1	0	1	0	0	1	0
1	1	0	1	0	0	0

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

1.  x1 /\x2  \/  x3 /\x4  \/   x5 /\x6

2.  x1 /\x3  \/  x4 /\x5  \/   x6 /\x2

3.  x1 /\x4  \/  x2 /\x5  \/   x6 /\x3

4.  x1 /\x5  \/  x2 /\x3  \/   x6 /\x4

Правильный ответ: 4

Замечание к решению. В принципе, любую подобную задачу можно решить, вычислив значение каждого из 4-х предложенных выражений на каждом из 3-х наборов значений переменных. Но часто можно вычисления упростить, если обратить внимание на особенности заданных выражений, значений переменных и соответствующих значений функции F. Таких особенностей много, заучивать их смысла нет. Но порешать разные задачи полезно. Советую также потренироваться в вычислении значений различных логических выражений при различных значениях переменных.

Решение. Выражение F должно быть ложно на всех заданных наборах. Все заданные выражения – дизъюнкции трех членов. Если хоть один из этих членов (каждый из них – конъюнкция) истинен на одном из наборов, то соответствующая дизъюнкция тоже истинна и, значит, это выражение не годится. В первых трех выражениях такие члены есть, это первые члены соответствующих дизъюнкций. А именно,

1.  x1 /\x2  - истинно на 1-м наборе;

2.  x1 /\x3  - истинно на 2-м наборе;

3.  x1 /\x4  - истинно на 3-м наборе.

Осталось проверить 4-е выражение. Входящие в него конъюнкции x1 /\x5; x2 /\x3 и x6 /\x4 ложны на всех трех заданных наборах значений переменных. Поэтому 4-е выражение подходит.

Ответ 4