С помощью карт карно»

 

Цель работы: научиться получать простейшие формулы, используя карты Карно.

 

Ход выполнения работы:

 

1. Изучить теоретический материал.

2. Получить задание у преподавателя.

3. Выполнить задание.

4. Ответить на контрольные вопросы.

5. Защитить выполненное задание.

 

Краткие теоретические сведения

Конъюнктивный одночлен от переменных Х ₁, Х ₂,..., Х_n – конъюнкция этих переменных или их отрицаний, при этом в конъюнктивный одночлен может входить одновременно и переменная, и ее отрицание.

Дизъюнктивный одночлен от переменных Х ₁, Х ₂,..., X_n – дизъюнкция этих переменных или их отрицаний, при этом в дизъюнктивный одночлен может входить одновременно и переменная, и ее отрицание.

Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция конъюнктивных одночленов , где конъюнктивные одночлены не обязательно различны.

Конъюнктивная нормальная форма (КНФ) – конъюнкция дизъюнктивных одночленов  , где дизъюнктивные одночлены не обязательно различны.

Карта Карно – графический способ минимизации формул алгебры высказываний.

Карты Карно удобны при небольшом числе переменных.

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

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

Согласно принятой форме построения карт соседними также считаются клетки первой и последней строк, клетки первого и последнего столбцов.

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

Соседние клетки карты Карно можно группировать для исключения переменной. Число группируемых клеток может быть и больше двух, но их число должно быть четным и они должны соприкасаться (являться соседними) друг с другом.

Допускается также иметь несколько групп перекрывающихся клеток.

Группироваться могут также клетки первой и последней строк, первого и последнего столбцов (карту допускается сворачивать в цилиндр как по вертикальной, так и по горизонтальной оси).

Для исключения n переменных общее число группируемых клеток должно быть равно 2 ⁿ. Так, для исключения одной переменной требуется объединить две соседние клетки, а для исключения трех переменных уже требуется объединить восемь соседних клеток.

Таким образом, для того чтобы получить минимизированную формулу, необходимо сгруппировать все соседние клетки карты Карно, содержащие 1 (или 0), а затем объединить полученные группы с помощью операции дизъюнкции (соответственно конъюнкции). Клетки, содержащие 1 (или 0), которые не удалось объединить с другими клетками, образуют в минимизированной формуле самостоятельные члены, каждый из которых содержит все переменные.

В результате будет получена минимальная ДНФ (если объединялись клетки с 1) или КНФ (если объединялись клетки с 0) соответственно

 

Образец выполнения

 

1. Найти простейшую формулу от трёх переменных, принимающую значение 0 только на следующих наборах значений переменных:

 

 

Решение

 

Составим карту Карно для трёх переменных

 

		00	01	11	10
	0	0			0
	1		0	0

 

Группируя клетки, содержащие 0, получаем:

в результате группировки клеток в 1-й строке дизъюнктивный одночлен X₁ÚX₃

в результате группировки клеток во 2-й строке дизъюнктивный одночлен ØX₁ÚØX₃

Окончательно получаем формулу вида F = (X₁ÚX₃)Ù(ØX₁ÚØX₃)

 

2. Найти простейшую формулу от трёх переменных, принимающую значение 1 только на следующих наборах значений переменных:

 

 

Решение

 

Составим карту Карно для трёх переменных

 

		00	01	11	10
	0	1			1
	1		1	1

 

Группируя клетки, содержащие 0, получаем:

в результате группировки клеток в 1-й строке конъюнктивный одночлен ØX₁ÙØX₃

в результате группировки клеток во 2-й строке конъюнктивный одночлен X₁ÙX₃

Окончательно получаем формулу вида F = (X₁ÙX₃)Ú(ØX₁ÙØX₃)

3. Получить простейшую формулу от четырёх переменных (в виде минимальной КНФ и минимальной ДНФ), если столбец значений этой формулы имеет вид:

 

1001 1001 1100 0111

 

Решение

 

Составим карту Карно для четырёх переменных

 

		00	01	11	10
	00	1	0	1	0
	01	1	0	1	0
	11	0	1	1	1
	10	1	1	0	0

 

Группируем единицы: первые две в 1-м столбце, последние две во втором столбце, первые две в 4-й строке, последние две в 3-й строке и первые две в 3-м столбце.

Получаем минимальную ДНФ:

 

F = (ØX₁ÙØX₃ÙØX₄)Ú(X₁ÙX₃ÙX₄)Ú(X₁ÙØX₂ÙØX₃)Ú(X₁ÙX₂ÙX₃)Ú(ØX₁ÙX₃ÙX₄)

 

Группируем нули: первые два во 2-м столбце, первые два в 4-м столбце, последние два в 4-м столбце.

Получаем минимальную КНФ:

 

F = (X₁ÚX₃ÚØX₄)Ù(X₁ÚØX₃ÚX₄)Ù(ØX₁ÚX₂ÚØX₃)Ù(ØX₁ÚØX₂ÚX₃ÚX₄)

 

Задания.

 

1. Найти простейшую формулу от трёх переменных, принимающую значение 0 только на следующих наборах значений переменных:

 

1)

2)

3)

4)

5)

6)

7)

8)

9)

 

2. Найти простейшую формулу от трёх переменных, принимающую значение 1 только на следующих наборах значений переменных:

 

1)

2)

3)

4)

5)

6)

7)

8)

9)

 

3. Получить простейшую формулу от четырёх переменных (в виде минимальной КНФ и минимальной ДНФ), если столбец значений этой формулы имеет вид:

 

1) 1001100001100001

2) 0100100011111111

3) 1010101010111110

4) 0000001110000011

5) 1111001010011110

6) 1000011100100010

7) 1100111110101111

8) 0000001110010101

9)   1110111001110111

 

Контрольные вопросы.

 

1. Что такое конъюнктивный одночлен.

2. Что такое дизъюнктивный одночлен.

3. Что такое конъюнктивная нормальная форма.

4. Что такое дизъюнктивная нормальная форма.

5. Как с помощью карты Карно получить минимальную ДНФ.

6. Как с помощью карты Карно получить минимальную КНФ.