,
"A compound proposition is composed of one or more simple propositions, and the way it is synthesized is called a 'connective word'. For example, 'This card is not a slave', 'This card is a man over 16 years old',' This card is a person originally from Fujian or Hainan', which are three compound propositions."
"The first proposition is a negation of the simple proposition 'This card is a slave', and the synthesis method is 'no'; the second proposition is composed of 'This card is a person over 16 years old' and' This card is composed of two simple propositions, and the synthesis method is 'and', that is, when two simple propositions are 'true' at the same time, the compound proposition is 'true'; and the third proposition is composed of 'this card It is composed of two simple propositions: "I am a person originally from Fujian" and "This card is a person originally from Hainan". The synthesis method is "or", that is, when any one of the two simple propositions is "true", the compound proposition is " real'."
"So, we have three means of connecting multiple propositions to make them into larger propositions, and, or, and not. There are actually two other methods, but they are not related to the design of the classification machine for the time being, so we will skip them here."
"We use symbols to represent propositions and connectives, then any query can be expressed as an expression. Obviously, the card that makes the expression 'true' is the card we are looking for. And the role of the classification machine is, It is to judge whether this expression is 'true' for all cards."
"Therefore, any expression that our classifier can judge as 'true/false' is a problem that we can solve. Any expression that our classifier cannot judge as true or false is a problem that we cannot solve."
"This is our initial abstraction of the problem."
Vonn wrote several strange symbols v (or), ∧ (and), and ┐ (not) on the blackboard. They looked like greater than signs and less than signs rotated 90 degrees, as well as inverted Latin letters. l.
"Okay, now you can write
The expression of the proposition 'people originally from Fujian or Hainan' is 100 for Hainan and 122 for Fujian, so we make
Proposition a: 'The first digit of the area code is 1',
Proposition b: 'The second digit of the area code is 0',
Proposition c: 'The third digit of the area code is 0',
Proposition d: 'The second digit of the area code is 2',
Proposition e: 'The third digit of the area code is 2',
Then, the expression of the compound proposition is: '(a∧b∧c)v(a∧d∧e)'. "
"How does our sorting machine determine the truth or falsehood? It is by checking whether the punched card is perforated. In other words, each card reading unit of the sorting machine can determine the truth or falsehood of a simple proposition in a compound proposition. At the same time, by With a control relay, we can allow each card reading unit to determine the true or false of a compound proposition with only one 'not' connective, that is, a non-proposition of a simple proposition."
"If we only had 1 card reading unit, that's it. But now we have 10 card reading units, so things are a little more complicated. But it can still be analyzed. Please pay attention to the Card pocket, features of loaded cards:
The cards in the card bag numbered k are the 'and', 'and' and 'k' propositions of the 'not' propositions of propositions 1~k-1.
The remaining cards that have passed through the card reading unit No. k are the 'AND's of the 'not' propositions that satisfy the propositions judged by No. 1~k.
The cards in the card bag numbered 1~k, together, satisfy the 'or' of the proposition judged by numbered 1~k.
Suppose that the simple propositions (or non-propositions of simple propositions) judged by our card reading unit are p1, p2,, p10.
Then the propositional expression we can judge is:
Card pocket No. 1: p1
Card pocket No. 2: ┐p1∧p2
Card pocket No. 3: ┐p1∧┐p2∧p3
Card pocket No. 4: ┐p1∧┐p2∧┐p3∧p4
Card bag No. 10: ┐p1∧┐p2∧∧┐p9∧p10
Final remaining cards: ┐p1∧┐p2∧∧┐p10
Finally, since these cards are separated from each other, we can finally freely choose the cards from any number of card pockets to be combined, which is the 'or' between the above expressions; the most important of which is the continuous number from 1 to k When the cards in k card pockets are put together, the result is: p1vvpk, that is, the continuous 'OR' operation starting with p1;
The remaining cards on the machine after passing through the card reading unit No. k can be expressed as ┐p1∧∧┐pk, which is a continuous 'AND' operation starting with ┐p1. "
"So, any proposition that can be transformed into the above formal expression can be searched by the classification machine, otherwise, it cannot be searched by the classification machine."
"The question I asked Kanai, to find the cards in the Sanya region except slaves, can be broken down into the following simple propositions or non-propositions of simple propositions:
Proposition a: 'The first digit of the area code is not 1',
Proposition b: 'The second digit of the area code is not 0',
Proposition c: 'The third digit of the area code is not 0',
Proposition d: 'The fourth digit of the area code is not 1',
Proposition e: 'The fifth digit of the area code is 1',
Proposition f: 'The fifth digit of the area code is not 2'
Proposition g: 'The 6th digit of the area code is not 9'
Proposition h: 'The 7th digit of the area code is not 9'
┐a∧┐b∧┐c∧┐d∧e, this is 10011, Yulin, Sanya, which conforms to the expression of card bag No. 5, so these cards are in card bag No. 5 and can be recorded as p5.
┐a∧┐b∧┐c∧┐d∧┐e∧┐f∧g, this is 100120~100128, Sanya Tiandu 11~89 Commune, it conforms to the expression of card bag No. 7, so these cards are located at No. 7 In the card pocket, it can be recorded as p7.
┐a∧┐b∧┐c∧┐d∧┐e∧┐f∧┐g∧h, this is 1001290~1001298, Sanya Tiandu 90~98 Commune, it conforms to the expression of card bag No. 8, so these cards It is located in card pocket No. 8 and can be recorded as p8.
The latter two combined, that is, p7vp8, is Sanya Tiandu, but does not include slaves. The combination of all three, namely p5vp7vp8, is the result we want. Because this expression conforms to our form above, the classifier can solve it. "
"And '(a∧b∧c)v(a∧d∧e)', no matter how we transform it, cannot be transformed into the above expression, so it cannot be solved by the current classification machine."
"Okay, here's the question, how to change the expression?" At this time, he looked at Feng Shan.
"This is the Boolean algebra of 0 and 1." Feng Shan replied, with a look of fascination in her eyes.
Feng Nuo nodded. Qian Yuzhi and Li Janai were completely confused before, but after hearing Boolean algebra, they somewhat came to their senses.
Vonn only taught them the simplest Boolean algebra, so that they thought Boolean algebra was Boolean algebra of 0 and 1.
"Then what?" Feng Nuo continued to guide.
"Boolean algebra is a complemented lattice! The intersection operation is 'and', the union operation is 'or', the complement operation is 'not', and satisfies the commutative law, associative law, and absorption law, and 'and' and 'or' each other It satisfies the distributive law! 0-1 Boolean algebra also satisfies the idempotent law!”
This is the theoretical part of Boolean algebra, and Qian Yuzhi and Li Ganai were confused again.
"Very good." Feng Nuo praised.
"However," he added, "the basic operational laws of the lattice are only between the two operations of 'and' and 'or', including commutative law, associative law, absorption law, idempotent law, distributive law, etc. In In propositional logic, we also need to consider the nature of 'not'. Here I will only talk about two points for now: First, the law of double negation. Obviously, the non-proposition of a proposition is itself. The form of its expression is - —”
Vonn wrote on the blackboard:
┐┐a=a;
"Second, virtue...well, let's call it the 'and or conversion law'. The negation of the conjunction of two propositions is the disjunction of the negation of two propositions; the negation of the disjunction of two propositions is the negation of two propositions. The conjunction of the negations of propositions. The form of its expression is——"
He also wrote:
┐(a∧b)=┐av┐b,
┐(avb)=┐a∧┐b.
"I'll give you two examples and you'll understand. 'Not a man over 16 years old' means 'a person under 16 years old' or a 'woman'; 'Not a person originally from Hainan or Fujian' means a 'person who is not originally from Hainan or Fujian' "Not from Hainan" and "Not from Fujian".
Then he continued, "According to these operational laws, the expressions of logical propositions can be transformed into various forms. However, generally we will transform into 'OR' of continuous 'AND', or 'AND' of continuous 'OR', They are called disjunctive normal form and conjunctive normal form.”
"Well, with theoretical tools, we can find that there are limitations in the design of current classification machines. If the classification machine can handle the general disjunctive paradigm or conjunctive paradigm, there will be no problems that cannot be solved by design. ——For example, 'find people who are originally from Fujian or Hainan'."
"This requires that each of our card reading units can not only judge the truth or falsehood of a simple proposition, but also be able to judge the truth or falsehood of the conjunction or disjunction composed of multiple simple propositions. This is reflected in the design of the classification machine , which is to transform the simple circuit in which the card reading unit currently only includes one working relay and one control relay into a switching circuit containing multiple relays."
"Yu Zhi, you have become very familiar with circuits during this time. Come and assemble a circuit with two switches and a light bulb. The requirement is that 'the light bulb will light up only when both switches are closed'."
Feng Nuo pointed to the workbench beside him. There was a mass of wires, relays, light bulbs, and switches on the workbench. Two bulky clock batteries lay beneath the bench. A multimeter and a few other instruments were thrown into the corner of the workbench.
Qian Yuzhi came to the workbench skillfully and got busy. He first led out the wires from the positive and negative terminals of the battery, and then connected the light bulb to the circuit, and the light bulb lit up. Then, he connected the two switches with wires, and connected them to the light bulb and battery.
Feng Nuo asked three students to try to see if the light bulb would only light up when two switches were closed. If any one switch was open, the light bulb would go out.
-------------------------------
Next update: Volume 7 - Strategy for Guangdong and Guangxi Chapter 61
