Để chuyển đổi logic bậc nhất sang CNF:
- Chuyển sang dạng phủ định thông thường. Loại bỏ các hàm ý và tương đương: thay thế nhiều lần bằng; thay thế bằng. …
- Chuẩn hóa các biến. …
- Bỏ qua câu lệnh. …
- Bỏ tất cả các định lượng phổ quát.
- Phân phối OR vào trong trên AND: thay thế nhiều lần bằng.
Công thức CNF là gì?
Dạng chuẩn liên kết (CNF) làmột cách tiếp cận logic Boolean biểu thị công thức dưới dạng liên từ của mệnh đề với AND hoặc OR. Mỗi mệnh đề được kết nối bằng một liên kết, hoặc AND, phải là một nghĩa đen hoặc chứa một phép tách hoặc toán tử OR. CNF hữu ích cho việc chứng minh định lý tự động.
Bạn có thể chuyển đổi DNF sang CNF không?
Nếu bạn muốn giới thiệu các biến bổ sung, bạn có thể chuyển đổi từ dạng DNF sang CNF trong thời gian đa thức bằng cáchbằng cách sử dụng biến đổi Tseitin. Công thức CNF kết quả sẽ tương đương với công thức DNF ban đầu: công thức CNF sẽ thỏa mãn nếu và chỉ khi công thức DNF ban đầu là thỏa mãn.
Tôi có thể nhận CNF bằng cách nào?
Chỉ cần viết ra bảng sự thật, khá đơn giản để tìm và suy ra CNF và DNF của bạn. Nếu bạn muốn tìm DNF, bạn phải xem tất cả các hàng kết thúc bằng T. Khi bạn tìm thấy các hàng đó, hãy lấy các giá trị x, y và z từ mỗi cột tương ứng. Do đó, bạn nhận được (x∧y∧z) ∨ (x∧¬y∧¬z) ∨ (¬x∧y∧¬z) ∨ (¬x∧¬y∧z).
Làm cách nào để bạn chuyển đổi disjunctive thànhdạng bình thường?
Một mệnh đề ghép được cho là ở dạng chuẩn tắc, hoặc DNF, nếu nó là phép ghépcủa các liên từ của các thuật ngữ đơn giảnvà nếu, hơn nữa, mỗi mệnh đề biến xuất hiện nhiều nhất một lần trong mỗi liên kết và mỗi liên kết xuất hiện nhiều nhất một lần trong liên kết.
