Применение к релейно-контактным схемам.

В этом параграфе мы рассмотрим одно техническое приложение булевых функций, которое оправдывает одно их название - переключательные функции.

Релейно-контактные (переключательные) схемы представляют собой схематическое изображение устройства, состоящее из следующих элементов:

1) переключателей, которыми могут быть механические устройства, электромагнитные реле и т.д.;

2) проводники, соединяющие переключатели;

3) входы в систему и выходы из неё, называемы полюсами.

На входы подаётся электрический сигнал. Переключатели могут быть замкнуты или разомкнуты, и в зависимости от общего состояния переключателей на выходе сигнал может сниматься либо нет.

Простейшая схема состоит из одного переключателя, одного входа и одного выхода. Поставим ему в соответствие высказывание р: «Переключатель замкнут». Если это высказывание истинно, то сигнал, поступающий на вход А, снимается на выходе В. В случае ложного высказывания сигнала на выходе нет. Это означает, что переключатель разомкнут. Такая простейшая схема приведена на рис. 3.

Более сложным высказываниям соответствуют более сложные схемы. Так, можно рассматривать отрицание вышеприведённого высказывания, соответствующее схеме, у которой на выходе сигнала не будет в случае, когда переключатель замкнут.

Конъюнкции p&q ставится в соответствие последовательное соединение двух простых схем (рис.4), дизъюнкции pÚq - параллельное соединение (рис. 5).

Так как любая формула может быть записана с помощью операции отрицания, дизъюнкции и конъюнкции, то любой формуле соответствует некоторая переключательная схема. Обратно, любой схеме соответствует некоторая схема. Это даёт возможность анализировать произвольную схему, записав её в виде некоторой формулы. Анализ может заключаться, например, в том, будет работать или нет данная схема. Или, нельзя ли упростить её без ущерба работоспособности.

Пример 7.1. Построим преключательную схему для формулы x(y ÚxyÚx ). Очевидно, формулу можно упростить: x(y ÚxyÚx )~x(yÚ ). Поэтому схема имеет вид, изображённый на рис. 6.

Упражнение 7.1. Составить переключательную схему для формул упражнения 3.4.

Упражнение 7.2. Составить переключательные схемы для функций упражнения 5.1.

Упражнение 7.3. Упростить схемы:

б)

в)

г)

Решение. а) Схема имеет следующую формулу ((х Úу)ÚуÚ(ху))х, упрощая которую, получаем ((х Úу)ÚуÚ(ху))х~xy. Поэтому в упрощённом виде схема выглядит так:

В заключение отметим, что с помощью булевых функций можно упрощать не только электрические схемы, но и всё, что может быть по аналогии интерпретировано с помощью булевых функций. Например, системы труб (для воды, нефти, газа) или схемы уличного движения.

Приложение 1

Варианты индивидуальных заданий

Вариант 1

1. Составить таблицу истинности формул (xÚy)«(y¯ ), (x| )®(zÅ ). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы x®(yÅz) и (x®y)Å(x®z):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

3. С помощью эквивалентных преобразований приведите формулу (xÚ )®( Å ) к ДНФ, КНФ, СДНФ, СКНФ. Построить полином Жегалкина.

4. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(0, 1, 1)=f(1, 1, 0)=f(1, 0, 1)=0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (1101 1000 1001 0111).

6. Является ли полной система функций ={xÚy, Åy}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: AÅ(BÅC)=(AÅB)ÅC.

Вариант 2

1. Составить таблицу истинности формул (x« )Ú (y¯x), ((x ® )| ) Å . Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы x|(y®z) и (x|y)®(x|z):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

3. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Построить полином Жегалкина.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 1, 1)=f(1, 0, 0)=f(1, 1, 0)=0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (0110 1010 1100 1100).

6. Является ли полной система функций ={x®y, Ù }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: A\(BÈC)=(A\B)Ç(A\C).

Вариант 3

1. Составить таблицу истинности формул (xÚ )«(y¯x), ((x | )® )Å . Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(yÅz) и (xÙy)Å(xÙz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 0)=f(0, 0, 1)=f(1, 0, 1)=f(1, 1, 1)=1. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (1011 1010 1001 1001).

6. Является ли полной система функций ={x«y, | }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: A\(BÇC)=(A\B)È(A\C).

Вариант 4

1. Составить таблицу истинности формул (x« )Ú(y¯x), ((x® )| )Å . Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(yÅz) и (xÙy)Å(xÙz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 1)=f(1, 1, 1)=f(1, 1, 0)= 1. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (0101 1110 1101 1101).

6. Является ли полной система функций ={xÅy, Úy}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: AÇ(BÅC)=(AÇB)Å(AÇC).

Вариант 5

1. Составить таблицу истинности формул (xÚ )®(yÅx), ((x« )| )¯ . Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(y®z) и (xÙy)®(xÙz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ булевой функции f(0, 0, 0)=f(1, 1, 1)=f(1, 1, 0)=0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (1111 1010 1011 0001).

6. Является ли полной система функций ={xÅy, Úy}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (AÇB)\C=(A\C)Ç(B\C).

Вариант 6

1. Составить таблицу истинности формул (xÅ )«(y|x), ((x¯ )« )Ú . Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(y®z) и (xÙy)«(xÙz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 1)=f(0, 1, 1)=f(1, 1, 0)=f(1, 1, 1)=1. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (1001 1011 1100 0101).

6. Является ли полной система функций ={x| , «y}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (A\B)\C=A\(BÈC).

Вариант 7

1. Составить таблицу истинности формул (xÚ )¯(y®x), ((x| )« )Å . Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(y|z) и (xÙy)|(xÙz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ булевой функции f(0, 0, 0)=f(1, 1, 1)=f(1, 0, 1)= 0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (0011 0001 1101 1010).

6. Является ли полной система функций ={xÅ , Úy}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: A\(B\C)=(A\B)È(AÇC).

Вариант 8

1. Составить таблицу истинности формул (xÅ )®(y¯x), ((x| )Ú )« . Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(y®z) и (xÚy)®(xÚz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ булевой функции f(1, 0, 1)=f(0, 1, 0)=f(1, 1, 1)=0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (1101 0101 0101 1111).

6. Является ли полной система функций ={x® , Ùy}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: AÈ(B\C)=(AÈB)\(C\A).

Вариант 9

1. Составить таблицу истинности формул «(y®( ¯x)), (( |y)Ú )Å . Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÚ(y|z) и (xÚy)|(xÚz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ булевой функции f(1, 0, 0)=f(0, 1, 1)=f(1, 1, 0)=f(0, 1, 0)=1. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (0001 0111 1101 1001).

6. Является ли полной система функций ={x« , |y}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: AÇ(B\C)=(AÇB)\(AÇC).

Вариант 10

1. Составить таблицу истинности формул x¯( ®(y|x)), xÅ( Ú « ). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÚ(y«z) и (xÚy)«(xÚz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ булевой функции f(0, 1, 1)=f(1, 0, 0)=f(1, 0, 1)=0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (1001 0101 0101 1011).

6. Является ли полной система функций ={ Å , xÚ }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (AÇB)\C=(A\C)Ç(B\C).

Вариант 11

1. Составить таблицу истинности формул «( ®(yÅx)), x |( Ú ¯ ). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÅ(y«z) и (xÅy)|(xÅz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 1)=f(1, 0, 0)=f(1, 1, 0)=0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (0100 1111 0001 1010).

6. Является ли полной система функций ={xÙy, ® }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (AÈB)\C=(A\C)È(B\C).

Вариант 12

1. Составить таблицу истинности формул x®( |(yÅx)), x«( Ú ¯ ). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÅ(y®z) и (xÅy)|(xÅz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 1)=f(0, 1, 1)=f(1, 1, 1)= 0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (0111 1001 0101 1110).

6. Является ли полной система функций ={x|y, « }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: A\(BÇC)=(A\B)È(A\C).

Вариант 13

1. Составить таблицу истинности формул x¯( ®(yÚx)), x|( « Å ). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÅ(y|z) и (xÅy)|(xÅz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 0)=f(0, 0, 1)=f(1, 1, 0)= 0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (1101 0011 1101 1000).

6. Является ли полной система функций ={ Åy, Ú }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (AÇB)\C=(A\C)Ç(B\C).

Вариант 14

1. Составить таблицу истинности формул xÅ( ®(y«x)), x¯( Ú | ). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы x¯(y«z) и (x¯y)«(x¯z):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 0)=f(0, 1, 0)=f(1, 1, 1)=0. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (0101 1010 0101 1010).

6. Является ли полной система функций ={xÙy, x ® }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В: A\B=AÅ(AÇB)

Вариант 15

1. Составить таблицу истинности формул (x¯y)|(yÚ ), (x« )Å(z® ). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы x|(yÅz) и (x|y)Å(x|z):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 0)=f(0, 0, 1)=f(1, 0, 0)=f(1, 1, 0)=1. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (0001 1110 0101 1011).

6. Является ли полной система функций ={xÚ y, «y}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В: AÇB=( ÈB)ÇA.

Вариант 16

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÅ(y«z) и (xÅy)|(xÅz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

6. Является ли полной система функций ={ Åy, Ú }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (AÇB)\C=(A\C)Ç(B\C).

Вариант 17

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(y®z) и (xÚy)®(xÚz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

6. Является ли полной система функций ={x«y, | }? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (AÇB)\C=(A\C)Ç(B\C).

Вариант 18

2. Проверить двумя способами, будут ли эквивалентны следующие формулы x|(yÅz) и (x|y)Å(x|z):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

6. Является ли полной система функций ={x| , «y}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: AÈ(B\C)=(AÈB)\(C\A).

Вариант 19

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(y®z) и (xÙy)«(xÙz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

6. Является ли полной система функций ={xÅy, Úy}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: A\(BÇC)=(A\B)È(A\C).

Вариант 20

2. Проверить двумя способами, будут ли эквивалентны следующие формулы xÙ(y®z) и (xÙy)«(xÙz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

Предыдущая 1 2 3 4 5 6 78Следующая

Не нашли, что искали? Воспользуйтесь поиском по сайту: