Карта Карно
Карта Карно — таблица истинности определённого вида для логической функции.
Была предложена в 1952 г. американским учёным Эдвардом В. Вейчем и усовершенствована в 1953 году американским физиком Морисом Карно.
Карты Карно используются для минимизации нормальной формы булевых функций, т.е. для построения МДНФ и МКНФ.
Виды карт Карно:[править]
Для функции двух переменных[править]
Для функции трёх переменных[править]
Для функции четырёх переменных[править]
- Заметим, что в картах Карно наборы аргументов в соседних строках и столбцах (включая первые и последние) отличаются значением одного аргумента.
- Для функций пяти и шести аргументов можно применять трёхмерную карту Карно.
Примеры использования карт Карно:[править]
Функция двух переменных[править]
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(x_1,x_2)=(0110)}
Строим карту Карно для функции двух переменных
Построение МДНФ[править]
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Единицы карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным конъюнкциям двух аргументов.
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P_1(x_1,x_2)=\{(1,2)\}}
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P_2(x_1,x_2)=\{(2,1)\}}
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_{\text{МДНФ}}(x_1,x_2)=\left(\bar{x}_1 \land x_2\right)\lor\left(x_1 \land \bar{x}_2\right)}
Построение МКНФ[править]
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Нули карты Карно минимально покрываются двумя прямоугольниками вида 1х1, что соответствует двум элементарным дизъюнкциям двух аргументов.
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P_1(x_1,x_2)=\{(1,1)\}}
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle P_2(x_1,x_2)=\{(2,2)\}}
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_{\text{КДНФ}}(x_1,x_2)=\left(x_1 \lor x_2\right)\land\left(\bar{x}_1 \lor \bar{x}_2\right)}
Функция трёх переменных[править]
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(x_1,x_2,x_3)=(01001101)}
Строим карту Карно для функции трёх переменных
Построение МДНФ[править]
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Единицы карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что два неполных прямоугольника вида 2х1 соответствуют одному полному прямоугольнику покрытия.
Построение МКНФ[править]
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.
Функция четырёх переменных[править]
Строим карту Карно для функции четырёх переменных
Построение МДНФ[править]
Покрываем единицы карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Единицы карты Карно минимально покрываются тремя квадратами вида 2х2, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что четыре угловых неполных квадрата соответствуют одному полному квадрату покрытия.
Построение МКНФ[править]
Покрываем нули карты Карно наименьшим числом прямоугольников со сторонами длиной 2n.
Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.
Другие понятия[править]
- Логический закон;
- Логические функции:
- Нормальные формы:
- Таблица истинности;
- Карта Карно;
- Трёхмерная карта Карно;
- Предикат;
- Секвенции;
- Суждение;
- Умозаключения:
- силогизмы: