Lời giải của phương trình logic. Giải một phương trình logic

Cách giải một số vấn đề trong Phần A và B của Kỳ thi Khoa học Máy tính

Bài số 3. Lôgic học. Các chức năng logic. Giải phương trình

Một số lượng lớn các nhiệm vụ USE được dành cho logic của các mệnh đề. Để giải hầu hết chúng, chỉ cần biết các luật cơ bản của logic mệnh đề, kiến ​​thức về bảng chân trị của các hàm logic một và hai biến là đủ. Tôi sẽ đưa ra các định luật cơ bản của logic mệnh đề.

1. Tính giao hoán của phép tách và phép kết hợp:
   a ˅ b ≡ b ˅ a
   a ^ b ≡ b ^ a
2. Luật phân phối liên quan đến sự tách rời và sự kết hợp:
   a ˅ (b ^ c) ≡ (a ˅ b) ^ (a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Phủ định của phủ định:
   ¬ (¬a) ≡ a
4. Tính nhất quán:
   a ^ ¬a ≡ sai
5. Thứ ba độc quyền:
   a ˅ ¬a ≡ đúng
6. Định luật De Morgan:
   ¬ (a ˅ b) ≡ ¬a ˄ ¬b
   ¬ (a ˄ b) ≡ ¬a ˅ ¬b
7. Đơn giản hóa:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ true ≡ a
   a ˄ false ≡ false
8. Hấp thụ:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Thay thế hàm ý
   a → b ≡ ¬a ˅ b
10. Thay đổi danh tính
    a ≡ b ≡ (a ˄ b) ˅ (¬a ˄ ¬b)

Biểu diễn các hàm logic

Bất kỳ hàm logic nào của n biến - F (x 1, x 2, ... x n) có thể được xác định bằng bảng chân trị. Một bảng như vậy chứa 2 n bộ biến, với mỗi giá trị của hàm trên tập này được chỉ định. Phương pháp này tốt khi số lượng biến tương đối ít. Ngay cả đối với n> 5, biểu diễn trở nên kém hiển thị.

Một cách khác là xác định hàm theo một số công thức, sử dụng các hàm khá đơn giản nổi tiếng. Hệ thống các hàm (f 1, f 2,… f k) được gọi là hoàn chỉnh nếu bất kỳ hàm logic nào có thể được biểu diễn bằng công thức chỉ chứa các hàm f i.

Hệ thống các hàm (¬, ˄, ˅) hoàn chỉnh. Luật 9 và 10 là những ví dụ về cách thể hiện hàm ý và bản sắc thông qua phủ định, kết hợp và tách rời.

Trên thực tế, hệ thống hai chức năng cũng hoàn chỉnh - phủ định và kết hợp hoặc phủ định và loại bỏ. Các trình bày tuân theo các luật của De Morgan cho phép thể hiện sự liên kết thông qua phủ định và loại bỏ, do đó, thể hiện một sự liên kết thông qua phủ định và kết hợp:

(a ˅ b) ≡ ¬ (¬a ˄ ¬b)
(a ˄ b) ≡ ¬ (¬a ˅ ¬b)

Nghịch lý thay, một hệ thống chỉ bao gồm một chức năng là hoàn chỉnh. Có hai hàm nhị phân - chống liên kết và chống liên kết, được gọi là mũi tên của Pierce và đột quỵ của Schaeffer, đại diện cho một hệ thống rỗng.

Các chức năng cơ bản của ngôn ngữ lập trình thường bao gồm nhận dạng, phủ định, kết hợp và phân loại. Trong các nhiệm vụ của kỳ thi, cùng với các chức năng này, thường có một hàm ý.

Hãy xem xét một vài nhiệm vụ đơn giản liên quan đến các hàm logic.

Nhiệm vụ 15:

Một phần của bảng sự thật được đưa ra. Hàm nào trong ba hàm đã cho tương ứng với đoạn này?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Tính năng số 3.

Để giải quyết vấn đề, bạn cần biết các bảng sự thật của các hàm cơ bản và ghi nhớ mức độ ưu tiên của các phép toán. Hãy để tôi nhắc bạn rằng phép kết hợp (phép nhân logic) có mức độ ưu tiên cao hơn và được thực hiện trước phép kết hợp (phép cộng logic). Khi tính toán, chúng ta dễ dàng nhận thấy rằng các hàm có số 1 và số 2 trên tập thứ ba có giá trị là 1 và vì lý do này không tương ứng với phân mảnh.

Nhiệm vụ 16:

Số nào sau đây thỏa mãn điều kiện:

(chữ số, bắt đầu bằng chữ số có nghĩa nhất, theo thứ tự giảm dần) → (số - chẵn) ˄ (chữ số thấp nhất - chẵn) ˄ (chữ số cao nhất - lẻ)

Nếu có một số con số như vậy, hãy chỉ ra con số lớn nhất.

1. 13579
2. 97531
3. 24678
4. 15386

Điều kiện được thỏa mãn bởi số 4.

Hai số đầu tiên không thỏa mãn điều kiện vì chữ số thấp nhất là số lẻ. Một kết hợp của các điều kiện là sai nếu một trong các điều khoản của kết hợp là sai. Đối với số thứ ba, điều kiện cho chữ số cao nhất không được đáp ứng. Đối với số thứ tư, các điều kiện áp dụng cho các chữ số chính và phụ của số được đáp ứng. Thuật ngữ đầu tiên của liên kết cũng đúng, vì một hàm ý là đúng nếu tiền đề của nó là sai, đó là trường hợp ở đây.

Bài toán 17: Hai nhân chứng làm chứng như sau:

Nhân chứng thứ nhất: Nếu A có tội, thì B chắc chắn có tội, và C vô tội.

Nhân chứng thứ hai: Hai người có tội. Và một trong những người còn lại chắc chắn có tội và có tội, nhưng tôi không thể nói chính xác là ai.

Từ các chứng cứ có thể rút ra kết luận gì về tội của A, B, C?

Trả lời: Theo lời khai thì A và B có tội, nhưng C vô tội.

Giải pháp: Tất nhiên, câu trả lời có thể được đưa ra dựa trên cảm nhận thông thường. Nhưng chúng ta hãy xem làm thế nào điều này có thể được thực hiện một cách nghiêm ngặt và chính thức.

Điều đầu tiên cần làm là chính thức hóa các câu lệnh. Hãy giới thiệu ba biến Boolean, A, B và C, mỗi biến đều đúng (1) nếu nghi phạm tương ứng có tội. Sau đó, lời khai của nhân chứng đầu tiên được đưa ra theo công thức:

A → (B ˄ ¬C)

Lời khai của nhân chứng thứ hai được đưa ra theo công thức:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Lời khai của cả hai nhân chứng được cho là đúng và thể hiện sự kết hợp của các công thức tương ứng.

Hãy xây dựng một bảng sự thật cho những bài đọc này:

Bằng chứng tóm tắt chỉ đúng trong một trường hợp, dẫn đến một câu trả lời rõ ràng - A và B có tội, và C vô tội.

Cũng theo phân tích bảng này, lời khai của nhân chứng thứ hai có nhiều thông tin hơn. Từ sự thật trong lời khai của anh ta, chỉ có hai lựa chọn khả thi sau - A và B có tội, và C vô tội, hoặc A và C có tội, và B vô tội. Lời khai của nhân chứng đầu tiên ít thông tin hơn - có 5 lựa chọn khác nhau tương ứng với lời khai của anh ta. Cùng với nhau, lời khai của cả hai nhân chứng đưa ra câu trả lời rõ ràng về tội ác của các nghi phạm.

Phương trình logic và hệ phương trình

Gọi F (x 1, x 2,… x n) là một hàm logic gồm n biến. Phương trình logic là:

F (x 1, x 2, ... x n) \ u003d C,

Hằng số C có giá trị 1 hoặc 0.

Một phương trình logic có thể có từ 0 đến 2n nghiệm khác nhau. Nếu C bằng 1 thì các nghiệm là tất cả các tập biến từ bảng chân trị mà hàm F nhận giá trị true (1). Các tập còn lại là nghiệm của phương trình đối với C bằng không. Chúng ta luôn chỉ có thể coi các phương trình có dạng:

F (x 1, x 2,… x n) = 1

Thật vậy, hãy cho phương trình đã cho:

F (x 1, x 2,… x n) = 0

Trong trường hợp này, bạn có thể chuyển sang phương trình tương đương:

¬F (x 1, x 2,… x n) = 1

Xét một hệ k phương trình logic:

F 1 (x 1, x 2, ... x n) \ u003d 1

F 2 (x 1, x 2, ... x n) \ u003d 1

F k (x 1, x 2,… x n) = 1

Nghiệm của hệ thống là một tập hợp các biến mà trên đó tất cả các phương trình của hệ thống đều được thỏa mãn. Về mặt hàm logic, để có được lời giải cho hệ phương trình logic, người ta phải tìm một tập hợp mà hàm logic Ф là đúng, đại diện cho tổ hợp của các hàm ban đầu F:

Ф = F 1 ˄ F 2 ˄… F k

Nếu số lượng biến nhỏ, chẳng hạn, nhỏ hơn 5, thì không khó để xây dựng bảng chân trị cho hàm Ф, cho phép bạn nói hệ có bao nhiêu nghiệm và đâu là các tập đưa ra nghiệm.

Trong một số nhiệm vụ của Bài kiểm tra trạng thái thống nhất về tìm lời giải cho một hệ phương trình logic, số biến đạt đến giá trị 10. Khi đó việc xây dựng một bảng chân trị trở thành một nhiệm vụ gần như nan giải. Giải quyết vấn đề đòi hỏi một cách tiếp cận khác. Đối với một hệ phương trình tùy ý, không có cách tổng quát nào khác ngoài phép liệt kê, cho phép giải những bài toán như vậy.

Trong các bài toán được đề xuất trong đề thi, cách giải thường dựa trên việc tính đến các đặc điểm cụ thể của hệ phương trình. Tôi nhắc lại, ngoài việc liệt kê tất cả các biến thể của một tập hợp các biến, không có cách chung nào để giải quyết vấn đề. Giải pháp phải được xây dựng dựa trên các chi tiết cụ thể của hệ thống. Nó thường hữu ích để thực hiện đơn giản hóa sơ bộ một hệ thống phương trình bằng cách sử dụng các định luật logic đã biết. Một kỹ thuật hữu ích khác để giải quyết vấn đề này như sau. Chúng tôi không quan tâm đến tất cả các tập hợp, mà chỉ quan tâm đến những tập hợp mà hàm Ф có giá trị 1. Thay vì xây dựng một bảng chân lý hoàn chỉnh, chúng tôi sẽ xây dựng tương tự của nó - một cây quyết định nhị phân. Mỗi nhánh của cây này tương ứng với một nghiệm và xác định một tập mà trên đó hàm Ф có giá trị 1. Số nhánh trong cây quyết định trùng với số nghiệm của hệ phương trình.

Cây quyết định nhị phân là gì và nó được xây dựng như thế nào, tôi sẽ giải thích bằng các ví dụ về một số nhiệm vụ.

Bài toán 18

Có bao nhiêu bộ giá trị khác nhau của các biến boolean x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 thỏa mãn một hệ hai phương trình?

Trả lời: Hệ thống có 36 cách giải khác nhau.

Lời giải: Hệ phương trình gồm hai phương trình. Hãy tìm số nghiệm của phương trình thứ nhất, phụ thuộc vào 5 biến - x 1, x 2,… x 5. Phương trình thứ nhất có thể coi là một hệ gồm 5 phương trình. Như đã được trình bày, hệ phương trình thực sự biểu diễn sự kết hợp của các hàm logic. Câu ngược cũng đúng - sự kết hợp của các điều kiện có thể được coi là một hệ phương trình.

Hãy xây dựng cây quyết định cho hàm ý (x1 → x2), số hạng đầu tiên của phép kết hợp, có thể được coi là phương trình đầu tiên. Đây là hình ảnh đại diện của cây này trông như thế nào:

Cây bao gồm hai cấp theo số lượng biến trong phương trình. Mức đầu tiên mô tả biến đầu tiên X 1. Hai nhánh của mức này phản ánh các giá trị có thể có của biến này - 1 và 0. Ở mức thứ hai, các nhánh của cây chỉ phản ánh những giá trị có thể có của biến X 2 mà phương trình nhận giá trị đúng. Vì phương trình xác định hàm ý, nhánh mà X 1 có giá trị 1 yêu cầu X 2 có giá trị 1. Trên nhánh đó. Nhánh mà X 1 có giá trị 0 tạo ra hai nhánh có X 2 giá trị bằng 0 và 1 Cây đã xây dựng xác định ba nghiệm, trong đó hàm ý X 1 → X 2 nhận giá trị 1. Trên mỗi nhánh, tập giá trị tương ứng của các biến được viết ra, đưa ra nghiệm của phương trình.

Các bộ này là: ((1, 1), (0, 1), (0, 0))

Hãy tiếp tục xây dựng cây quyết định bằng cách thêm vào phương trình sau, hàm ý sau X 2 → X 3. Đặc thù của hệ phương trình là mỗi phương trình mới của hệ sử dụng một biến từ phương trình trước, thêm một biến mới. Vì biến X 2 đã có giá trị trong cây, nên trên tất cả các nhánh mà biến X 2 có giá trị 1, biến X 3 cũng sẽ có giá trị 1. Đối với các nhánh như vậy, việc xây dựng cây tiếp tục cấp độ tiếp theo, nhưng không có chi nhánh mới xuất hiện. Nhánh duy nhất mà biến X 2 có giá trị 0 sẽ cho một nhánh thành hai nhánh, trong đó biến X 3 sẽ nhận các giá trị 0 và 1. Do đó, mỗi phép cộng của một phương trình mới, với tính chất cụ thể của nó, sẽ thêm một giải pháp. Phương trình đầu tiên ban đầu:

(x1 → x2) / \ (x2 → x3) / \ (x3 → x4) / \ (x4 → x5) = 1
có 6 giải pháp. Đây là cây quyết định hoàn chỉnh cho phương trình này trông như thế nào:

Phương trình thứ hai của hệ thống của chúng tôi tương tự như phương trình đầu tiên:

(y1 → y2) / \ (y2 → y3) / \ (y3 → y4) / \ (y4 → y5) = 1

Điểm khác biệt duy nhất là phương trình sử dụng các biến Y. Phương trình này cũng có 6 nghiệm. Vì mỗi nghiệm biến X i có thể kết hợp với mỗi nghiệm biến Y j nên tổng số nghiệm là 36.

Lưu ý rằng cây quyết định được xây dựng không chỉ cung cấp số lượng giải pháp (theo số nhánh), mà còn cung cấp chính các giải pháp, được viết ra trên mỗi nhánh của cây.

Bài toán 19

Có bao nhiêu bộ giá trị khác nhau của các biến boolean x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 thỏa mãn tất cả các điều kiện sau?

(x1 → x2) / \ (x2 → x3) / \ (x3 → x4) / \ (x4 → x5) = 1
(y1 → y2) / \ (y2 → y3) / \ (y3 → y4) / \ (y4 → y5) = 1
(x1 → y1) = 1

Nhiệm vụ này là một sửa đổi của nhiệm vụ trước đó. Sự khác biệt là một phương trình khác được thêm vào có liên quan đến các biến X và Y.

Từ phương trình X 1 → Y 1 suy ra rằng khi X 1 có giá trị 1 (tồn tại một nghiệm như vậy) thì Y 1 có giá trị 1. Như vậy, tồn tại một tập hợp X 1 và Y 1 có giá trị là 1. Khi X 1 bằng 0, Y 1 có thể có giá trị bất kỳ, cả 0 và 1. Do đó, mỗi tập X 1 bằng 0 và có 5 tập hợp như vậy, tương ứng với tất cả 6 tập hợp có biến Y. Do đó , tổng số nghiệm là 31.

Bài toán 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Giải: Nhớ lại sự tương đương cơ bản, chúng ta viết phương trình của chúng ta dưới dạng:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Chuỗi hàm ý tuần hoàn có nghĩa là các biến giống hệt nhau, vì vậy phương trình của chúng ta tương đương với:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Phương trình này có hai nghiệm khi tất cả X i đều là 1 hoặc 0.

Bài toán 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Giải pháp: Cũng giống như trong Bài toán 20, chúng ta chuyển từ hàm ý tuần hoàn sang đồng nhất bằng cách viết lại phương trình dưới dạng:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Hãy xây dựng một cây quyết định cho phương trình này:

Bài toán 22

Hệ phương trình sau có bao nhiêu nghiệm?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅ (¬ (X 1 ≡X 2) ˄ ¬ (X 3 ≡X4)) = 0

((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅ (¬ (X 3 ≡X 4) ˄ ¬ (X5 ≡X 6)) = 0

((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅ (¬ (X5 ≡X 6) ˄ ¬ (X 7 ≡X8)) = 0

((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅ (¬ (X 7 ≡X 8) ˄ ¬ (X9 ≡X10)) = 0

Trả lời: 64

Giải pháp: Chuyển từ 10 biến thành 5 biến bằng cách giới thiệu sự thay đổi của các biến sau:

Y 1 = (X 1 ≡ X 2); Y 2 \ u003d (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 \ u003d (X 7 ≡ X 8); Y 5 \ u003d (X 9 ≡ X 10);

Khi đó phương trình đầu tiên sẽ có dạng:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Phương trình có thể được đơn giản hóa bằng cách viết nó thành:

(Y 1 ≡ Y 2) = 0

Chuyển sang dạng truyền thống, chúng tôi viết hệ thống sau khi đơn giản hóa ở dạng:

¬ (Y 1 ≡ Y 2) = 1

¬ (Y 2 ≡ Y 3) = 1

¬ (Y 3 ≡ Y 4) = 1

¬ (Y 4 ≡ Y 5) = 1

Cây quyết định cho hệ thống này rất đơn giản và bao gồm hai nhánh với các giá trị thay đổi xen kẽ:

Quay lại với các biến X ban đầu, lưu ý rằng mỗi giá trị của biến Y tương ứng với 2 giá trị của biến X, vì vậy mỗi nghiệm trong các biến Y tạo ra 2 5 nghiệm trong các biến X. Hai nhánh tạo ra 2 * 2 5 nghiệm , do đó tổng số nghiệm là 64.

Như bạn có thể thấy, mỗi nhiệm vụ để giải một hệ phương trình yêu cầu cách tiếp cận riêng của nó. Một thủ thuật phổ biến là thực hiện các phép biến đổi tương đương để đơn giản hóa các phương trình. Một kỹ thuật phổ biến là xây dựng cây quyết định. Cách tiếp cận được áp dụng một phần giống với việc xây dựng bảng chân trị với điểm đặc biệt là không phải tất cả các bộ giá trị có thể có của các biến đều được xây dựng, mà chỉ những bộ mà hàm nhận giá trị 1 (đúng). Thông thường, trong các bài toán đề xuất, không cần thiết phải xây dựng một cây quyết định hoàn chỉnh, vì đã có ở giai đoạn đầu, có thể thiết lập tính đều đặn của sự xuất hiện của các nhánh mới ở mỗi cấp độ tiếp theo, ví dụ như trong bài toán 18. .

Nhìn chung, các bài toán tìm lời giải cho một hệ phương trình logic là những bài tập toán hay.

Nếu bài toán khó giải bằng tay, bạn có thể giao lời giải cho máy tính bằng cách viết một chương trình thích hợp để giải phương trình và hệ phương trình.

Rất dễ dàng để viết một chương trình như vậy. Một chương trình như vậy sẽ dễ dàng đối phó với tất cả các nhiệm vụ được cung cấp trong kỳ thi.

Kỳ lạ là, nhiệm vụ tìm lời giải cho các hệ phương trình logic cũng khó đối với máy tính, hóa ra máy tính cũng có giới hạn của nó. Máy tính có thể dễ dàng đối phó với các nhiệm vụ có số lượng biến là 20-30, nhưng nó sẽ bắt đầu suy nghĩ rất lâu về các nhiệm vụ lớn hơn. Vấn đề ở đây là hàm 2 n xác định số bộ là một số mũ tăng nhanh với n. Nhanh đến mức một máy tính cá nhân bình thường không thể xử lý một tác vụ với 40 biến trong một ngày.

Chương trình C # để giải các phương trình logic

Sẽ rất hữu ích nếu bạn viết một chương trình giải các phương trình logic vì nhiều lý do, nếu chỉ vì nó có thể được sử dụng để kiểm tra tính đúng đắn của lời giải của riêng bạn đối với các bài toán kiểm tra USE. Một lý do khác là chương trình như vậy là một ví dụ tuyệt vời về một bài toán lập trình đáp ứng các yêu cầu cho các bài toán loại C trong SỬ DỤNG.

Ý tưởng xây dựng một chương trình rất đơn giản - nó dựa trên việc liệt kê đầy đủ tất cả các bộ giá trị biến có thể có. Vì số biến n được biết đến đối với một phương trình hoặc hệ phương trình logic nhất định, nên số bộ cũng được biết - 2 n, cần được sắp xếp. Sử dụng các chức năng cơ bản của ngôn ngữ C # - phủ định, tách rời, kết hợp và đồng nhất, có thể dễ dàng viết một chương trình, đối với một tập biến nhất định, tính giá trị của một hàm logic tương ứng với một phương trình logic hoặc hệ phương trình.

Trong một chương trình như vậy, bạn cần phải xây dựng một chu trình bằng số bộ, trong phần thân của chu trình, bằng số bộ, tự tạo thành bộ, tính giá trị của hàm trên bộ này và nếu giá trị này bằng 1 thì tập nghiệm cho phương trình.

Khó khăn duy nhất nảy sinh trong quá trình thực hiện chương trình liên quan đến nhiệm vụ hình thành tập các giá trị biến chính nó bằng số đã đặt. Cái hay của nhiệm vụ này là trên thực tế, nhiệm vụ có vẻ khó khăn này lại trở thành một nhiệm vụ đơn giản đã phát sinh nhiều lần. Thật vậy, đủ để hiểu rằng tập hợp các giá trị của các biến tương ứng với số i, bao gồm các số không và số một, thể hiện sự biểu diễn nhị phân của số i. Vì vậy, nhiệm vụ phức tạp của việc lấy một tập hợp các giá trị của các biến theo số đã đặt được rút gọn thành bài toán nổi tiếng về chuyển một số thành một hệ nhị phân.

Đây là cách hàm C # giải quyết vấn đề của chúng ta trông giống như sau:

///

///

/// hàm logic - phương thức,

/// có chữ ký được đặt bởi đại diện DF

///

/// số lượng biến

/// số lượng giải pháp

static int SolveEquations (DF fun, int n)

bool set = new bool [n];

int m = (int) Math.Pow (2, n); // số bộ

int p = 0, q = 0, k = 0;

// Liệt kê đầy đủ theo số bộ

for (int i = 0; i< m; i++)

// Hình thành tập tiếp theo - set,

// được cho bởi biểu diễn nhị phân của số i

for (int j = 0; j< n; j++)

k = (int) Math.Pow (2, j);

// Tính giá trị hàm trên set

Để hiểu chương trình, tôi hy vọng rằng các giải thích về ý tưởng của chương trình và các nhận xét trong văn bản của nó là đủ. Tôi sẽ chỉ tập trung vào phần giải thích về tiêu đề của hàm trên. Hàm SolveEquations có hai tham số đầu vào. Tham số vui chỉ định một hàm logic tương ứng với phương trình hoặc hệ phương trình đang được giải. Tham số n chỉ định số lượng biến trong hàm fun. Kết quả là, hàm SolveEquations trả về số lượng nghiệm của hàm logic, tức là số bộ mà hàm đánh giá là true.

Đối với học sinh, thông thường khi đối với một số hàm F (x), tham số đầu vào x là một biến kiểu số học, chuỗi hoặc kiểu boolean. Trong trường hợp của chúng tôi, một thiết kế mạnh mẽ hơn được sử dụng. Hàm SolveEquations đề cập đến các hàm bậc cao - các hàm kiểu F (f), có tham số không chỉ là các biến đơn giản mà còn là các hàm.

Lớp hàm có thể được truyền dưới dạng tham số cho hàm SolveEquations được định nghĩa như sau:

đại biểu bool DF (bool vars);

Lớp này bao gồm tất cả các hàm được truyền dưới dạng tham số, một tập hợp các giá trị của các biến boolean được chỉ định bởi mảng vars. Kết quả là một giá trị Boolean đại diện cho giá trị của hàm trên tập hợp này.

Cuối cùng, tôi sẽ đưa ra một chương trình trong đó hàm SolveEquations được sử dụng để giải một số hệ phương trình logic. Hàm SolveEquations là một phần của lớp ProgramCommon sau:

Chương trình lớp học

đại biểu bool DF (bool vars);

static void Main (chuỗi args)

Console.WriteLine ("Chức năng và Giải pháp -" +

SolveEquations (FunAnd, 2));

Console.WriteLine ("Hàm có 51 giải pháp -" +

SolveEquations (Fun51, 5));

Console.WriteLine ("Hàm có 53 giải pháp -" +

SolveEquations (Fun53, 10));

bool tĩnh FunAnd (bool vars)

trả lại vars && vars;

bool tĩnh Fun51 (bool vars)

f = f && (! vars || vars);

f = f && (! vars || vars);

f = f && (! vars || vars);

f = f && (! vars || vars);

f = f && (! vars || vars);

bool tĩnh Fun53 ​​(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (! ((vars == vars) || (vars == vars)));

Đây là kết quả của giải pháp cho chương trình này trông như thế nào:

10 nhiệm vụ cho công việc độc lập

1. Hàm nào trong ba hàm tương đương:
   1. (X → Y) ˅ ¬Y
   2. ¬ (X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Một phần của bảng sự thật được đưa ra:

Chức năng nào trong số ba chức năng tương ứng với phân đoạn này:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Ban giám khảo gồm ba người. Quyết định được đưa ra nếu chủ tịch hội đồng giám khảo bỏ phiếu tán thành và được ít nhất một trong các thành viên ban giám khảo ủng hộ. Nếu không, không có quyết định nào được đưa ra. Xây dựng một hàm logic chính thức hóa quá trình ra quyết định.
5. X thắng Y nếu bốn lần tung đồng xu xuất hiện ba lần. Xác định một hàm boolean mô tả lợi nhuận X.
6. Các từ trong một câu được đánh số bắt đầu từ một. Một câu được coi là hay nếu đáp ứng các quy tắc sau:
   1. Nếu một từ được đánh số chẵn kết thúc bằng một nguyên âm, thì từ tiếp theo, nếu nó tồn tại, phải bắt đầu bằng một nguyên âm.
   2. Nếu một từ được đánh số lẻ kết thúc bằng một phụ âm, thì từ tiếp theo, nếu nó tồn tại, phải bắt đầu bằng một phụ âm và kết thúc bằng một nguyên âm.
      Câu nào đúng trong các câu sau:
   3. Mẹ đã rửa sạch Masha bằng xà phòng.
   4. Người lãnh đạo luôn là một hình mẫu.
   5. Sự thật là tốt, nhưng hạnh phúc còn hơn.
7. Phương trình có bao nhiêu nghiệm:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Liệt kê tất cả các nghiệm của phương trình:
   (a → b) → c = 0
9. Hệ phương trình sau có bao nhiêu nghiệm:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Phương trình có bao nhiêu nghiệm:
    (((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Câu trả lời cho các nhiệm vụ:

1. Các hàm b và c là tương đương.
2. Đoạn tương ứng với chức năng b.
3. Đặt biến boolean P nhận giá trị 1 khi chủ tịch hội đồng xét xử bỏ phiếu "tán thành" quyết định. Các biến M 1 và M 2 đại diện cho ý kiến ​​của các thành viên ban giám khảo. Hàm logic xác định việc thông qua một quyết định tích cực có thể được viết như sau:
   P ˄ (M 1 ˅ M 2)
4. Để biến boolean P i nhận giá trị 1 khi đồng xu thứ i xuất hiện. Hàm logic xác định lợi nhuận X có thể được viết như sau:
   ¬ ((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Chào hàng b.
6. Phương trình có 3 nghiệm: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Cơ sở giáo dục ngân sách thành phố

"Trường cấp 2 số 18"

quận nội thành của thành phố Salavat của Cộng hòa Bashkortostan

Hệ phương trình logic

trong nhiệm vụ của kỳ thi tin học

Phần "Cơ bản của Đại số Logic" trong các nhiệm vụ của kỳ thi được coi là một trong những phần khó và kém nhất. Tỷ lệ hoàn thành nhiệm vụ trung bình về chủ đề này là thấp nhất và là 43,2.

Dựa trên đặc điểm kỹ thuật của KIM 2018, khối này bao gồm bốn nhiệm vụ có mức độ phức tạp khác nhau.

Nhiệm vụ 23 là một cấp độ khó cao, do đó nó có tỷ lệ hoàn thành thấp nhất. Trong số các sinh viên tốt nghiệp được đào tạo (81-100 điểm) 49,8% hoàn thành, chuẩn bị trung bình (61-80 điểm) đạt 13,7%, nhóm còn lại sinh viên không hoàn thành nhiệm vụ này.

Sự thành công của việc giải một hệ phương trình logic phụ thuộc vào kiến ​​thức về các quy luật logic và vào việc áp dụng chính xác các phương pháp để giải hệ thống.

Xét nghiệm của một hệ phương trình logic bằng phương pháp ánh xạ.

(23.154 Polyakov K.Yu.) Hệ phương trình có bao nhiêu nghiệm khác nhau?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (y1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

ở đâu x1 , x2 ,…, x8, tại1 , y2 ,…, Y8 - Các biến Boolean? Câu trả lời không cần phải liệt kê tất cả các bộ giá trị biến khác nhau mà đẳng thức này giữ. Như một câu trả lời, bạn cần chỉ ra số lượng các bộ như vậy.

Giải pháp. Tất cả các phương trình có trong hệ thống đều thuộc cùng một loại và bốn biến số được bao gồm trong mỗi phương trình. Biết x1 và y1, ta có thể tìm được tất cả các giá trị có thể có của x2 và y2 thỏa mãn phương trình thứ nhất. Lập luận theo cách tương tự, từ x2 và y2 đã biết ta tìm được x3, y3 thoả mãn phương trình thứ hai. Tức là, khi biết cặp (x1, y1) và xác định giá trị của cặp (x2, y2), chúng ta sẽ tìm được cặp (x3, y3), từ đó sẽ dẫn đến cặp (x4, y4) và như vậy trên.

Hãy tìm tất cả các nghiệm của phương trình đầu tiên. Điều này có thể được thực hiện theo hai cách: xây dựng bảng chân lý, thông qua suy luận và áp dụng các quy luật logic.

Bảng sự thật:

Việc xây dựng một bảng sự thật tốn nhiều công sức và thời gian không hiệu quả, vì vậy chúng tôi sử dụng phương pháp thứ hai - suy luận logic. Sản phẩm là 1 nếu và chỉ khi mỗi hệ số là 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Hãy xem xét phương trình đầu tiên. Theo sau bằng 1, khi 0 0, 0 1, 1 1, thì (x1 y1) = 0 tại (01), (10), thì cặp (x2  y2 ) có thể là bất kỳ (00), (01), (10), (11) và đối với (x1 y1) = 1, tức là (00) và (11) cặp (x2 y2) = 1 nhận các giá trị giống nhau (00) và (11). Chúng tôi loại trừ khỏi giải pháp này những cặp mà phương trình thứ hai và thứ ba là sai, nghĩa là, x1 = 1, x2 = 0, y1 = 1, y2 = 0.

Tổng số cặp 1 + 1 + 1 + 22 = 25

2) (23.160 Polyakov K.Yu.) Một hệ phương trình logic có bao nhiêu nghiệm khác nhau

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Giải pháp. 1) Các phương trình cùng loại nên bằng phương pháp suy luận ta sẽ tìm được tất cả các cặp (x1, y1), (x2, y2) của phương trình thứ nhất.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Nghiệm của phương trình thứ hai là các cặp (00), (01), (11).

Hãy tìm nghiệm của phương trình đầu tiên. Nếu x1 = 0 thì x2, y2 - bất kỳ, nếu x1 = 1 thì x2, y2 nhận giá trị (11).

Hãy tạo mối liên hệ giữa các cặp (x1, y1) và (x2, y2).

Hãy lập bảng để tính số cặp ở mỗi giai đoạn.

Tính đến các nghiệm của phương trình cuối cùng x 7  y 7 = 1, chúng tôi loại bỏ cặp (10). Tìm tổng số nghiệm 1 + 7 + 0 + 34 = 42

3)(23.180) Hệ phương trình lôgic có bao nhiêu nghiệm khác nhau

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Giải pháp. 1) Các phương trình cùng loại nên bằng phương pháp suy luận ta sẽ tìm được tất cả các cặp (x1, x2), (x3, x4) của phương trình thứ nhất.

(x1  x2 )  (x3  x4 ) = 1

Chúng tôi loại trừ khỏi giải pháp các cặp cho 0 (1 0) sau đây, đây là các cặp (01, 00, 11) và (10).

Soạn liên kết giữa các cặp (x1, x2), (x3, x4)

Hướng dẫn. Khi nhập từ bàn phím, hãy sử dụng các quy ước sau:

Quy tắc nhập hàm logic

1. Sử dụng dấu + thay vì v (ngắt quãng, HOẶC).
2. Trước hàm logic, bạn không cần chỉ định hàm. Ví dụ, thay vì F (x, y) = (x | y) = (x ^ y), bạn chỉ cần nhập (x | y) = (x ^ y).
3. Số lượng biến tối đa là 10.

Việc thiết kế và phân tích các mạch logic máy tính được thực hiện với sự trợ giúp của một phần toán học đặc biệt - đại số logic. Trong logic đại số, có thể phân biệt ba hàm logic chính: "NOT" (phủ định), "AND" (kết hợp), "OR" (tách).
Để tạo bất kỳ thiết bị logic nào, cần phải xác định sự phụ thuộc của từng biến đầu ra vào các biến đầu vào hiện tại, sự phụ thuộc như vậy được gọi là hàm chuyển mạch hoặc hàm của đại số logic.
Một hàm đại số logic được gọi là xác định đầy đủ nếu cho trước tất cả 2 n giá trị của nó, trong đó n là số biến đầu ra.
Nếu không phải tất cả các giá trị đều được xác định, hàm được gọi là xác định một phần.
Một vùng nhớ được gọi là logic nếu trạng thái của nó được mô tả bằng cách sử dụng một hàm của logic đại số.
Các phương pháp sau được sử dụng để biểu diễn hàm đại số logic:
Ở dạng đại số, có thể xây dựng một sơ đồ của một thiết bị lôgic bằng cách sử dụng các phần tử lôgic.


Hình 1 - Sơ đồ của một thiết bị logic

Tất cả các hoạt động của đại số logic được định nghĩa bảng sự thật các giá trị. Bảng sự thật xác định kết quả của việc thực hiện một phép toán cho tất cả có thể x giá trị lôgic của các câu lệnh ban đầu. Số lượng các tùy chọn phản ánh kết quả của việc áp dụng các phép toán sẽ phụ thuộc vào số lượng câu lệnh trong biểu thức logic. Nếu số câu lệnh trong biểu thức logic là N, thì bảng sự thật sẽ chứa 2 N hàng, vì có 2 N kết hợp khác nhau của các giá trị đối số có thể có.

Hoạt động KHÔNG - phủ định lôgic (đảo ngược)

• nếu biểu thức ban đầu là true, thì kết quả của sự phủ định của nó sẽ là false;
• nếu biểu thức ban đầu là false, thì kết quả của sự phủ định của nó sẽ là true.

Hoạt động HOẶC - phép cộng hợp lý (nối, liên hợp)

Hoạt động AND - phép nhân logic (kết hợp)

Hoạt động "IF-THEN" - hệ quả logic (ngụ ý)

Hoạt động "A nếu và chỉ khi B" (tương đương, tương đương)

Hoạt động bổ sung Modulo 2 (XOR, độc quyền hoặc, ngắt kết nối nghiêm ngặt)

Mức độ ưu tiên của các phép toán logic

• Các thao tác trong ngoặc
• Nghịch đảo
• Sự liên kết (&)
• Disjunction (V), Exclusive OR (XOR), modulo 2 sum
• Hàm ý (→)
• Tương đương (↔)

Dạng bình thường hoàn hảo disjunctive

1. Mỗi số hạng logic của công thức chứa tất cả các biến có trong hàm F (x 1, x 2, ... x n).
2. Tất cả các điều khoản logic của công thức là khác nhau.
3. Không có thuật ngữ logic nào chứa một biến và sự phủ định của nó.
4. Không có số hạng logic nào trong công thức chứa cùng một biến hai lần.

Dạng bình thường liên kết hoàn hảo

1. Tất cả các hàm sơ cấp chứa tất cả các biến có trong hàm F (x 1, x 2, ... x n).
2. Tất cả các phép toán cơ bản là khác biệt.
3. Mỗi khớp nối cơ bản chứa một biến một lần.
4. Không có phép tách cơ bản nào chứa một biến và sự phủ định của nó.

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, trong đó J, K, L, M, N là các biến Boolean?

Giải pháp.

Biểu thức (N ∨ ¬N) đúng với N bất kỳ, vì vậy

J ∧ ¬K ∧ L ∧ ¬M = 0.

Áp dụng phủ định cho cả hai vế của phương trình logic và sử dụng định luật De Morgan ¬ (A ∧ B) = ¬ A ∨ ¬ B. Ta nhận được ¬J ∨ K ∨ ¬L ∨ M = 1.

Tổng logic bằng 1 nếu ít nhất một trong các câu lệnh cấu thành của nó bằng 1. Do đó, bất kỳ tổ hợp nào của các biến logic thỏa mãn phương trình kết quả, ngoại trừ trường hợp tất cả các đại lượng có trong phương trình bằng 0. Mỗi 4 biến có thể bằng 1 hoặc 0, do đó có thể có các tổ hợp 2 2 2 2 = 16. Do đó, phương trình có 16 −1 = 15 nghiệm.

Cần lưu ý rằng 15 nghiệm tìm được tương ứng với bất kỳ giá trị nào trong hai giá trị có thể có của các giá trị của biến logic N, vì vậy phương trình ban đầu có 30 nghiệm.

Trả lời: 30

Phương trình có bao nhiêu nghiệm khác nhau

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

trong đó J, K, L, M, N là các biến boolean?

Câu trả lời không cần phải liệt kê tất cả các bộ giá trị khác nhau J, K, L, M và N mà đẳng thức này giữ. Như một câu trả lời, bạn cần chỉ ra số lượng các bộ như vậy.

Giải pháp.

Chúng ta sử dụng các công thức A → B = ¬A ∨ B và ¬ (A ∨ B) = ¬A ∧ ¬B

Hãy xem xét biểu mẫu con đầu tiên:

(J → K) → (M ∧ N ∧ L) = ¬ (¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Hãy xem xét biểu đồ con thứ hai

(J ∧ ¬K) → ¬ (M ∧ N ∧ L) = ¬ (J ∧ ¬K) ∨ ¬ (M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Hãy xem xét biểu đồ con thứ ba

1) M → J = 1 do đó

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Phối hợp:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 do đó có 4 nghiệm.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Phối hợp:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L nên có 4 nghiệm.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Đáp số: 4 + 4 = 8.

Trả lời: 8

Phương trình có bao nhiêu nghiệm khác nhau

((K ∨ L) → (L ∧ M ∧ N)) = 0

trong đó K, L, M, N là các biến boolean? Câu trả lời không cần phải liệt kê tất cả các bộ giá trị K, L, M và N khác nhau mà đẳng thức này giữ. Là một Câu trả lời, bạn cần chỉ ra số lượng các bộ như vậy.

Giải pháp.

Hãy viết lại phương trình bằng cách sử dụng ký hiệu đơn giản hơn cho các hoạt động:

((K + L) → (L M N)) = 0

1) từ bảng chân lý của phép toán "hàm ý" (xem bài toán đầu tiên), nó theo sau rằng đẳng thức này đúng nếu và chỉ khi đồng thời

K + L = 1 và L M N = 0

2) nó theo sau từ phương trình đầu tiên rằng ít nhất một trong các biến, K hoặc L, bằng 1 (hoặc cả hai cùng nhau); vì vậy hãy xem xét ba trường hợp

3) nếu K = 1 và L = 0, thì đẳng thức thứ hai áp dụng cho M và N bất kỳ; vì có 4 sự kết hợp của hai biến boolean (00, 01, 10 và 11), chúng tôi có 4 nghiệm khác nhau

4) nếu K = 1 và L = 1, thì đẳng thức thứ hai áp dụng cho M · N = 0; có 3 tổ hợp như vậy (00, 01 và 10), ta có thêm 3 nghiệm nữa

5) nếu K = 0, thì nhất thiết phải L = 1 (từ phương trình đầu tiên); trong trường hợp này, đẳng thức thứ hai được thỏa mãn tại М · N = 0; có 3 tổ hợp như vậy (00, 01 và 10), ta có thêm 3 nghiệm nữa

6) tổng cộng ta nhận được 4 + 3 + 3 = 10 nghiệm.

Trả lời: 10

Phương trình có bao nhiêu nghiệm khác nhau

(K ∧ L) ∨ (M ∧ N) = 1

Giải pháp.

Biểu thức đúng trong ba trường hợp khi (K ∧ L) và (M ∧ N) lần lượt là 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N là 1, và K và L là bất kỳ, trừ cả 1. Do đó có 3 nghiệm.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 nghiệm.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 nghiệm.

Trả lời: 7.

Trả lời: 7

Phương trình có bao nhiêu nghiệm khác nhau

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0

trong đó X, Y, Z, P là các biến boolean? Câu trả lời không cần phải liệt kê tất cả các bộ giá trị khác nhau mà đẳng thức này có. Như một câu trả lời, bạn chỉ cần cung cấp số lượng các bộ như vậy.

Giải pháp.

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0 =>

¬ (X ∧ Y ∨ Z) ​​∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

OR logic chỉ sai trong một trường hợp: khi cả hai biểu thức đều sai.

Kể từ đây,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Do đó, chỉ có một nghiệm cho phương trình.

Trả lời 1

Phương trình có bao nhiêu nghiệm khác nhau

(K ∨ L) ∧ (M ∨ N) = 1

trong đó K, L, M, N là các biến boolean? Câu trả lời không cần phải liệt kê tất cả các bộ giá trị khác nhau của K, L, M và N mà đẳng thức này tồn tại. Như một câu trả lời, bạn chỉ cần cung cấp số lượng các bộ như vậy.

Giải pháp.

Hợp lý AND chỉ đúng trong một trường hợp: khi tất cả các biểu thức đều đúng.

K ∨ L = 1, M ∨ N = 1.

Mỗi phương trình cho 3 nghiệm.

Xét phương trình A ∧ B = 1 nếu cả A và B đều nhận giá trị đúng trong ba trường hợp, thì phương trình có 9 nghiệm tổng quát.

Do đó, câu trả lời là 9.

Trả lời: 9

Phương trình có bao nhiêu nghiệm khác nhau

((A → B) ∧ C) ∨ (D ∧ ¬D) = 1,

trong đó A, B, C, D là các biến boolean?

Câu trả lời không cần phải liệt kê tất cả các bộ giá trị A, B, C, D khác nhau mà đẳng thức này có. Như một câu trả lời, bạn cần xác định số lượng các bộ như vậy.

Giải pháp.

Lôgic "OR" là đúng khi ít nhất một trong các câu lệnh là đúng.

(D ∧ ¬D) = 0 với D bất kỳ.

Kể từ đây,

(A → B) ∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, cho ta 3 nghiệm với mỗi D.

(D ∧ ¬ D) = 0 với D bất kỳ, cho ta hai nghiệm (với D = 1, D = 0).

Do đó: tổng các nghiệm 2 * 3 = 6.

Tổng số 6 giải pháp.

Trả lời: 6

Phương trình có bao nhiêu nghiệm khác nhau

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

trong đó K, L, M, N là các biến boolean? Câu trả lời không cần phải liệt kê tất cả các bộ giá trị khác nhau của K, L, M và N mà đẳng thức này tồn tại. Như một câu trả lời, bạn chỉ cần cung cấp số lượng các bộ như vậy.

Giải pháp.

Áp dụng phủ định cho cả hai vế của phương trình:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

OR logic đúng trong ba trường hợp.

Lựa chọn 1.

K ∧ L ∧ M = 1 thì K, L, M = 1, và ¬L ∧ M ∧ N = 0. Bất kỳ N, tức là có 2 nghiệm.

Lựa chọn 2.

¬L ∧ M ∧ N = 1 thì N, M = 1; L = 0, K bất kỳ, tức là có 2 nghiệm.

Do đó, câu trả lời là 4.

Trả lời: 4

A, B và C là các số nguyên mà câu lệnh là đúng

¬ (A = B) ∧ ((A> B) → (B> C)) ∧ ((B> A) → (C> B)).

B sẽ bằng bao nhiêu nếu A = 45 và C = 43?

Giải pháp.

Lưu ý rằng câu lệnh phức tạp này bao gồm ba câu lệnh đơn giản.

1) ¬ (A = B); (A> B) → (B> C); (B> A) → (C> B);

2) các câu lệnh đơn giản này được kết nối với nhau bằng phép toán ∧ (AND, kết hợp), nghĩa là chúng phải được thực hiện đồng thời;

3) từ ¬ (А = B) = 1 nó ngay sau đó А B;

4) giả sử A> B thì từ điều kiện thứ hai ta thu được 1 → (B> C) = 1; biểu thức này có thể đúng nếu và chỉ khi B> C = 1;

5) do đó ta có A> B> C, chỉ có số 44 tương ứng với điều kiện này;

6) Chỉ trong trường hợp, hãy kiểm tra phương án A 0 → (B> C) = 1;

biểu thức này đúng với bất kỳ B; bây giờ chúng tôi xem xét điều kiện thứ ba, chúng tôi nhận được

biểu thức này có thể đúng nếu và chỉ khi C> B, và ở đây chúng ta có một mâu thuẫn, bởi vì không có số B như vậy mà C> B> A.

Trả lời: 44.

Trả lời: 44

Lập bảng chân trị cho một hàm logic

X = (A ↔ B) ∨ ¬ (A → (B ∨ C))

trong đó cột giá trị của đối số A là ký hiệu nhị phân của số 27, cột giá trị của đối số B là số 77, cột giá trị của đối số C là số 120. Số trong cột được viết từ trên xuống dưới từ chữ số có nghĩa nhất đến chữ số có nghĩa nhỏ nhất (kể cả tập hợp số 0). Chuyển đổi biểu diễn nhị phân kết quả của các giá trị của hàm X sang hệ thống số thập phân.

Giải pháp.

Chúng tôi viết phương trình bằng cách sử dụng ký hiệu đơn giản hơn cho các hoạt động:

1) đây là một biểu thức có ba biến, vì vậy sẽ có các dòng trong bảng chân trị; do đó, ký hiệu nhị phân của các số mà các cột của bảng A, B và C được xây dựng phải bao gồm 8 chữ số

2) chúng tôi sẽ dịch các số 27, 77 và 120 sang hệ nhị phân, ngay lập tức bổ sung mục nhập 8 ký tự có số 0 ở đầu các số

3) không chắc bạn sẽ có thể viết ngay các giá trị của hàm X cho mỗi kết hợp, vì vậy sẽ thuận tiện khi thêm các cột bổ sung vào bảng để tính toán các kết quả trung gian (xem bảng bên dưới)

4) điền vào các cột của bảng:

giá trị chỉ là 1 trong những dòng A = B

giá trị là 1 trong những dòng mà B hoặc C = 1

giá trị chỉ bằng 0 trong những hàng A = 1 và B + C = 0

giá trị là nghịch đảo của cột trước đó (0 được thay thế bằng 1 và 1 được thay thế bằng 0)

kết quả X (cột cuối cùng) là tổng hợp lý của hai cột và

5) để có câu trả lời, chúng tôi viết ra các bit từ cột X từ trên xuống dưới:

6) dịch số này sang hệ thập phân:

Trả lời: 171

Số nguyên X lớn nhất mà câu lệnh (10 (X + 1) · (X + 2)) là đúng là bao nhiêu?

Giải pháp.

Một phương trình là một phép toán hàm ý giữa hai mối quan hệ:

1) Tất nhiên, ở đây bạn có thể áp dụng phương pháp tương tự như trong ví dụ 2208, nhưng trong trường hợp này, bạn sẽ cần giải phương trình bậc hai (tôi không muốn ...);

2) Lưu ý rằng, với điều kiện, chúng ta chỉ quan tâm đến số nguyên, vì vậy bạn có thể cố gắng bằng cách nào đó biến đổi biểu thức ban đầu, thu được một câu lệnh tương đương (các giá trị chính xác của gốc không khiến chúng ta quan tâm!);

3) Xét bất đẳng thức: rõ ràng nó có thể là một số dương và một số âm;

4) Thật dễ dàng để kiểm tra xem câu lệnh có đúng với tất cả các số nguyên trong vùng và với tất cả các số nguyên trong vùng (để không bị nhầm lẫn, sẽ thuận tiện hơn khi sử dụng các bất đẳng thức không nghiêm ngặt và thay vì và );

5) Do đó, đối với số nguyên, nó có thể được thay thế bằng một biểu thức tương đương

6) vùng chân trị của một biểu thức là hợp của hai khoảng vô hạn;

7) Bây giờ hãy xem xét bất đẳng thức thứ hai: rõ ràng là nó cũng có thể là một số dương và một số âm;

8) Trong vùng, câu lệnh đúng với mọi số nguyên và trong vùng, với mọi số nguyên, do đó, đối với số nguyên, nó có thể được thay thế bằng một biểu thức tương đương

9) vùng chân trị của biểu thức là một khoảng đóng;

10) Biểu thức đã cho đúng ở mọi nơi, ngoại trừ các khu vực ở đó và;

11) Lưu ý rằng giá trị không còn phù hợp nữa, bởi vì ở đó và, nghĩa là, hàm ý cho 0;

12) Khi thay 2, (10 (2 + 1) · (2 ​​+ 2)), hoặc 0 → 0 thỏa mãn điều kiện.

Vì vậy, câu trả lời là 2.

Trả lời: 2

Số nguyên X lớn nhất mà mệnh đề đúng là bao nhiêu?

(50 (X + 1) (X + 1))?

Giải pháp.

Áp dụng phép biến đổi hàm ý và biến đổi biểu thức:

(50 (X + 1) (X + 1)) ⇔ ¬ (X 2> 50) ∨ ((X + 1) 2) ∨ (| X + 1 |).

Một OR logic đúng khi có ít nhất một câu lệnh logic đúng. Sau khi giải cả hai bất phương trình và xem xét chúng ta thấy rằng số nguyên lớn nhất mà ít nhất một trong số chúng đúng là 7 (trong hình bên, nghiệm dương của bất phương trình thứ hai được hiển thị bằng màu vàng và nghiệm thứ nhất có màu xanh lam) .

Trả lời: 7

Chỉ định giá trị của các biến K, L, M, N mà biểu thức logic

(¬ (M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

sai. Viết câu trả lời của bạn dưới dạng một chuỗi 4 ký tự: giá trị của các biến K, L, M và N (theo thứ tự đó). Vì vậy, ví dụ, dòng 1101 tương ứng với K = 1, L = 1, M = 0, N = 1.

Giải pháp.

Nhân bản nhiệm vụ 3584.

Trả lời: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Giải pháp.

Hãy áp dụng phép biến đổi hàm ý:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Áp dụng phủ định cho cả hai vế của phương trình:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Hãy biến đổi:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Do đó, M = 0, N = 0, xét bây giờ (¬K ∧ L ∨ M ∧ L):

thực tế là M = 0, N = 0 ngụ ý rằng M ∧ L = 0, khi đó ¬K ∧ L = 1, tức là K = 0, L = 1.

Trả lời: 0100

Chỉ định giá trị của các biến K, L, M, N mà biểu thức logic

(¬ (M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

sai. Viết câu trả lời của bạn dưới dạng một chuỗi bốn ký tự: giá trị của các biến K, L, M và N (theo thứ tự đó). Vì vậy, ví dụ, dòng 1101 tương ứng với K = 1, L = 1, M = 0, N = 1.

Giải pháp.

Hãy viết phương trình bằng cách sử dụng ký hiệu các phép toán đơn giản hơn (điều kiện "biểu thức là sai" có nghĩa là nó bằng 0 logic):

1) nó xuất phát từ câu lệnh điều kiện rằng biểu thức phải sai đối với chỉ một tập biến

2) từ bảng chân lý của phép toán "ngụ ý" rằng biểu thức này sai nếu và chỉ khi đồng thời

3) đẳng thức đầu tiên (tích logic bằng 1) đúng nếu và chỉ khi và; do đó nó theo sau (tổng logic bằng 0), chỉ có thể là khi; do đó, chúng tôi đã xác định ba biến

4) từ điều kiện thứ hai, cho và chúng tôi có được.

Công việc trùng lặp

Trả lời: 1000

Cho biết giá trị của các biến logic P, Q, S, T mà biểu thức logic

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) là sai.

Viết câu trả lời của bạn dưới dạng một chuỗi bốn ký tự: giá trị của các biến P, Q, S, T (theo thứ tự đó).

Giải pháp.

(1) (Р ∨ ¬Q) = 0

(2) (Q → (S ∨ T)) = 0

(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Áp dụng phép biến đổi hàm ý:

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Trả lời: 0100

Chỉ định giá trị của các biến K, L, M, N mà biểu thức logic

(K → M) ∨ (L ∧ K) ∨ ¬N

sai. Viết câu trả lời của bạn dưới dạng một chuỗi bốn ký tự: giá trị của các biến K, L, M và N (theo thứ tự đó). Vì vậy, ví dụ, dòng 1101 tương ứng với K = 1, L = 1, M = 0, N = 1.

Giải pháp.

Lôgic "OR" là sai nếu và chỉ khi cả hai câu lệnh đều sai.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Hãy áp dụng phép biến đổi hàm ý cho biểu thức đầu tiên:

¬K ∨ M = 0 => K = 1, M = 0.

Hãy xem xét biểu thức thứ hai:

(L ∧ K) ∨ ¬N = 0 (xem kết quả của biểu thức đầu tiên) => L ∨ ¬N = 0 => L = 0, N = 1.

Trả lời: 1001.

Trả lời: 1001

Chỉ định giá trị của các biến K, L, M, N mà biểu thức logic

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

đúng vậy. Viết câu trả lời của bạn dưới dạng một chuỗi bốn ký tự: giá trị của các biến K, L, M và N (theo thứ tự đó). Vì vậy, ví dụ, dòng 1101 tương ứng với K = 1, L = 1, M = 0, N = 1.

Giải pháp.

Lôgic "AND" là đúng nếu và chỉ khi cả hai câu lệnh đều đúng.

1) (K → M) = 1 Áp dụng phép biến đổi hàm ý: ¬K ∨ M = 1

2) (K → ¬M) = 1 Áp dụng phép biến đổi hàm ý: ¬K ∨ ¬M = 1

Điều này ngụ ý rằng K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Ta áp dụng phép biến đổi hàm ý: K ∨ (M ∧ ¬L ∧ N) = 1 từ thực tế rằng K = 0 ta nhận được.