Creating Logic, Part I: Beginning Logic Reading Notes

Creating Logic, Part I: Beginning Logic Reading Notes

Logic is the study of the way humans think and argue, and in particular, it deals with the basic concepts of propositions and reasoning.

The basic concepts of logic include propositions, propositional logic, and the symbolic system of logic. A proposition is a statement that is determined to be true or false. Propositional logic is the field of logic that deals with propositions and uses logical operators to represent logical relations. The symbol system of logic is a system that defines symbols to express logical operations, and in propositional logic, logical operators such as “negation,” “logical conjunction,” and “logical disjunction” are used.

In addition to propositional logic, there are other fields of logic such as first-order predicate logic and higher-order logic. First-order predicate logic is a type of propositional logic that can express more complex logical relations by introducing predicates and variables. Higher-order logic deals with logic involving mathematical concepts such as sets and functions.

Logic also includes the study of methods for determining the truth or falsehood of propositions and for making correct inferences. For example, there are methods of determining the truth or falsity of propositions, such as truth tables and proofs. The truth table is a method of determining the truth of a proposition by testing all possible combinations of truth and falsehood for the proposition. Proof is the logical procedure for showing that a proposition is true, using axioms and rules of inference to derive the truth of the proposition.

Logic is also closely related to philosophy, mathematics, artificial intelligence, and other fields. In philosophy, the concepts of logic are used to make logical arguments, and in mathematics, logic is used to construct the basic system for deriving mathematical propositions. In artificial intelligence, it is the basis for reasoning and knowledge information processing techniques.

Mathematical theories on which logic is based include set theory, as described in “Overview of Set Theory and Reference Books,” algebra, as described in “Structures, Algorithms, and Functions,” and formal linguistics and semantics, as described in “Formal Languages and Mathematical Logic,” which can be found at See also.

we present reading notes from “Making Logic,” a well-known textbook on mathematical logic.

In this article, I will discuss my reading notes from Part 1, Section 1: Beginning Logic.

Introduction

Part I. Getting Started with Logic

Chapter 1 What is THIS Thing called Logic?
1.1 What is Logic?　And What Does Logic Do?

1.1.1 How to Get Started is Actually Difficult
1.1.2 The Three Faces of Logic
Logic as the study of the correctness of arguments
The notion of flow and non-flow is the primary subject of logic.
Argument, inference
What does it mean that a certain conclusion can emerge from a certain premise?
Logic is the study of the concept of logical consequence.
A systematic study of what constitutes a good argument and how to distinguish good arguments from bad ones.
Logic as a collection of propositions, statements, and ideas
The second subject of logic
The second subject of logic
The concept of “inconsistency” or “non-inconsistency
A contradiction is said about a collection of statements (assertions).
When a collection of sentences is formed at once, the collection is said to be inconsistent or consistent.
Two faces are one.
The two issues of logic are actually two sides of the same thing.
Logic as Formal Truth
Logic as formal truth It is correct just because it has the form “either it is or it is not”.
The third goal of logic is to systematically study “what is formal truth, and how can we determine whether a statement is or is not formal truth?
Goals of Logic and Strategy of this Book
Three important concepts are explained
1.1.3 Is logic interesting?
What does logic bring to the table?
conjunction
Two words are connected by a rule and may or may not be murky.
I don’t understand the rules even when I use them
When a completely new combination of words is introduced that you have never encountered before, you can naturally distinguish between muddled and unmuddled words.
The mysterious status of logic
Research by Wayson and John Laird
(1) If Fox is a trustworthy man, then UFOs exist. Fox is a trustworthy man. Therefore, UFOs exist.
(2) If Fox is a trustworthy man, then UFOs exist. Therefore, Fox is not a trustworthy man.
Both (1) and (2) are correct as arguments.
People are much less good at judging the correctness of argument (2) than (1).
What mechanisms are used to make inferences?
What is the mechanism of the mind to recognize the correctness of logic?

1.2 Where should we look for the correctness of logic?

1.2.1 Distinguishing the correctness of an argument from the truth of a proposition
Correctness of Argument and Truth of Proposition
Example
1+1=2 The capital of Bosnia and Herzegovina is Sarajevo The sea anemone is a pharyngeal animal
All three propositions are true.
But they do not appear to be logical
It is better to distinguish between the correctness of an argument and the truth of a proposition.
An argument can be correct even if it contains false propositions.
A proposition can be false even if it consists only of true propositions.
Propositions can be “true/false”.
Correctness of an argument can be valid/invalid.
1.2.2 How to make a successful argument
You can trust the conclusion of an argument when
the argument is valid, and
and all of its premises are true.
Why study the validity of an argument alone?
The purpose of argumentation and reasoning is not just to derive another true proposition from what we already know to be true.
1.2.3 The Form of an Argument Determines Its Validity
For now, let’s check
What exactly is the validity of an argument as distinguished from the truth of its propositions?
There is no case where the premises are all true but the conclusion is false.
In other words, whether or not the premises are actually true, the conclusion cannot be false.
In other words, if all the premises are true, then the entire conclusion is also true.
The validity of an argument is not about the content of the argument, but about its form.
What should we look for in an argument to strictly distinguish between a valid argument and an invalid argument?
All zeros are ■■ All ■■ are XX ————————- All zeros are XX
1.2.4 Words that relate to the form of an argument and words that do not
The validity of an argument depends only on the meaning of words such as “all,” “not,” “or,” “if,” “every,” etc. that appear in it, and not on the meaning of other words.
Logical constant
Words such as “all,” “not,” “or,” “if,” “every,” etc. that are directly related to the correctness of an argument.
They can be classified into three groups
negative terms
Not.”
Conjunctions
or”, “if”.
Quantifiers
All”, “Every”, “a”

Chapter 2: Creating an Artificial Language for Logic
2.1 From Natural Language to Artificial Language

2.1.1 Why Logic Uses Artificial Languages
Modern logic uses an artificial language, called symbolic logic.
Use of artificial language
In natural languages, the logical form of a proposition can be overshadowed by the grammatical form.
2.1.2 How shall we proceed with symbolization?
Example
Tom is currently flea catching or taking a nap If Tom is taking a nap now, Jerry is taking a nap now Jerry is not taking a nap —————————————————————— Tom is flea catching “Jerry is napping right now.
Replace “Jerry is taking a nap right now” with a P
Tom is now flea catching or taking a nap If Tom is now napping, he is not P P —————————————————————— Tom is flea catching
Replace “Tom is taking a nap right now” with Q
If Tom is taking a flea now or Q Q then P P not —————————————————————— Tom is taking a flea
Replace “Tom is flea catching now” with R
If R or Q Q then not P P —————— R
Simple and compound propositions
A proposition expressed in a short affirmative sentence is the smallest unit of form.
P, Q, R
The simplest propositions
Each of the three premises is either two propositions joined by a conjunction such as “or” or “then”, or a simple proposition joined by “not”.
A more complex proposition made up of simple propositions.
What constitutes a simple proposition depends on what kind of argument you are dealing with and what form you are trying to get out of it.
2.1.3 Boolean Expressions and Boolean Combiners
The roles of “or,” “or,” “without difference,” and “or” are the same.
Similarly
If…
Not.
The final expression in the example is
R V Q Q→P ¬P ——– R
Logical structure
A symbolic representation of each proposition is called a well-formed formula (wff for short).
Simple propositions P, Q, and R are called “atomic formulas”.
Logical connectives
A symbolic representation of a conjunction or negation
Difference between “and” and “but”?
The same “Λ” is used for “xx and yet xx” and “xx and yet xx.
However, the emotional meaning in the sentence is different.
Symbolic logic eliminates them
Truth-functional connectives
There are many other ways in natural language to connect two or more propositions to form a compound proposition
The truth or falsity of the whole “because” is not uniquely determined by the truth or falsity of its constituent simple propositions.
So why limit yourself to “and”, “or”, “then”, and “not”?
Combiners such as “and” and “not” are called “truth-functional”.

2.2 Artificial Language L

2.2.1 Why should we define artificial languages properly?
A plausible question
The goal is to create an artificial language that is suitable for the purpose of clarifying the validity of arguments
What is the vocabulary and grammar of L(logic)?
Logic should be a universal study.
2.2.2 Defining an artificial language L
When defining an artificial language
Determine the range of vocabulary used in the language
Vocabulary of L
The vocabulary used in L can be divided into three groups
(1) Atomic formulas
P,Q,R,…
(2) Combiners
→, V, Λ, ¬,…
(3) Auxiliary symbols
(,)
Next, we need to define a grammar, that is, a set of rules for how to combine the vocabulary to obtain the compound expressions allowed in the language.
The grammar of L, i.e. the definition of logical expressions
(1) An atomic formula, i.e. P, Q, R,… are logical formulas.
(2) If A and B are logical formulas, then (AΛB), (AⅤB), (A→B), and (¬A) are logical formulas of each.
(3) Only formulas defined by (1) and (2) are logical formulas.
Inductive definition
Recursive definition
Why is the above a definition of a logical formula?
Tree of formation
1
2
What are A and B?
Meta-logical variable (meta-logical variable)
Another example of an inductive definition
Gradual formulas for sequences of numbers
2.2.3 What does it mean to define a logical formula inductively?
Proof by Mathematical Induction
For an inductively defined object, a unique proof method can be used
The main advantage of inductive definition
Proof by the functional method for the length of an expression
2.2.4 Unique Readabilitiy Theorem
2.2.5 Some Terms for the Form of Boolean Expressions
2.2.6 Let’s distinguish between syntax and semantics

Chapter 3 Giving Meaning to Artificial Languages — Semantics of Propositional Logic
3.1 The Meaning of Combiners and Truth Tables

Introduction
The correctness of an argument is related to the meaning of its connectives (logical definitions).
3.1.1 Truth table showing the meaning of “and
For the proposition “Vanessa is good at acting, and Vanessa is good at singing
How does the truth of the above compound proposition relate to the truth of the two atomic propositions?
Consider the truth table
The Bivalence Principle
In this book, we will limit truth values to two, true and false.
We adopt the principle of bivalence, which states that “all logical expressions always wait for a truth value of either true or false.
Many-valued logic
A logic that has more than one truth value, considering truth values such as “neither” or “unknown” in addition to true and false.
3.1.2 Meanings of other connectives can also be given in truth tables
Truth table 1
Truth table 2
Two types of selections
Question about “V
Japanese “or” often means only one of them
Exclusive disjunction
A V B includes the case where both A and B are true
Non-exclusive disjunction
The term “disjunction” means a non-exclusive disjunction.
If you think there’s something wrong with →, you’re in good company.
Look at the truth table that defines the condition “→”.
“If A, then B” means
True when A and B are both true
False when A is true and B is false
If the previous case A is false, then the subsequent case B is true regardless of whether it is true or false.
This is intuitively strange.
The use of “If A, then B” expects some kind of content connection between A and B.
We don’t often think in terms of the assumption that A is not A.
As long as we try to give meaning to the “→” in the truth table
If you want to give meaning to “→” in a truth table, you have to ignore the content connection and recommend only the truth value combination.
There is no way to approximate “if” using only truth-value combinations.
The best choice is to consider the following two factors
Approximating “if” to the extent that it serves the stated goals of logic.
The constraint that we must approximate “if” using only truth-value combinations and in a way that satisfies the two-valued principle.
A bogus explanation
A father promises his child that he will buy him an NES if he gets 100 points on the next math test.
The child gets 100 points and is bought an NES.
The father kept his promise.
You get 100 points, but the father does not buy you an NES.
The father reneges on his promise
I didn’t get 100 points, but he bought me an NES.
He didn’t break his promise.
I kept my promise.
I did not get 100 points, but my father did not buy me a NES.
I didn’t break my promise.
I kept my promise.

3.2 Truth-value analysis of logic expressions

3.2.1 How to do truth value analysis
By using a truth table to define the meaning of a conjunction, we can analyze when it becomes true for any logical expression (called the truth condition of the logical expression).
3.2.2 Adding New Combiners
Biconditional
A, if and only if B
(A→B)Λ(B→A) and truth table are the same
In our daily life, we use “if only”.
“If I don’t have 100 million yen by tomorrow, my son’s life will be forfeit.
If I have prepared 100 million yen (false) and my son is killed (true), I call him a liar (false)

3.3 Tautology

3.3.1 What is Tautology?
Boolean expressions can be classified into three types depending on when they become true
Tautology
Always 1, regardless of the truth value of the atomic formula contained in it.
Factual expressions
A formula that can be 1 or 0 depending on how the truth value of the atomic formula contained in it is taken
Contradiction formula
A formula that is always 0 regardless of the way the truth value of the atomic formula contained in it is taken.
Unsatisfiable formula
Tautologies and factoids contain expressions that may or may not always be 1, but can be 1 anyway.
3.3.2 Typical Tautologies
There are countless tautologies, but some of the most common patterns have names
law of identity
law of excluded middle
law 0f contradiction
idempotent law
Commutative law
associative law
Distributive law
Absorptive law
Do Mrgan’s law
Law of contraposition
Disjunctive syllogism
Transitive law
Modus pones
Modes tollens
Law of addition
Law of simplification
Law of importation
Law of exportation
Constructive dilemma
Law of addition
Perce’s law
Law of permutation
Law of composition
Note on the diagram
The above
Rather than being tautologies in themselves
A common type of logical formula that is a tautology.
3.3.3 What is tautology after all?
Tautology as Formal Truth
What is tautology?
A proposition that is true only in its form, regardless of the content of the constituent propositions.
A proposition that is formally true (more precisely, a proposition that is true only by virtue of a logical theorem).
Analytic truth and empirical truth
There are several kinds of “truths.
Examples
(1) If Spike Lee is a film director, then Spike Lee is a film director.
(2) If Spike Lee is a film director, then Spike Lee is a film maker.
(3) Spike Lee is a film director, and he also played the role of a pizza parlor clerk in his own film, Do the right thing.
(1),(2) can be shown to be correct only in words
Inevitable truth
(2) can only be done if you know the meaning of the word
(1), that is, tautology does not require the meaning of words
(3) can only be known through actual investigation
(3) can only be known through investigation, such as experimentation and observation.
True according to the state of the world
Truth that is true because of the way the world happens to be
Tautology and the amount of information
Tautology does not tell us anything about what is going on in reality

3.4 Capturing “What the heck, it’s not the same thing after all” — Logical equivalence

3.4.1 Definition of Logical Equivalence
When truth values are always the same
If the truth values are always the same, the two formulas are said to be logically equivalent.
Two logical expressions A and B are logically equivalent
⇔
A and B are always the same for any combination of the truth values of their constituent atomic formulas.
〜⇔˜⇔ ….
〜This is a short way of saying (or writing) the following. That is, ….
Note that it does not mix with ⟷.
A⫦⫣B
Logical formulas A and B are logical equivalences.
Contraposition
A → B and ¬B → ¬A
3.4.2 Equivalence transformation
The transformation of a logical formula A into another logical formula B that is logically equivalent to it.
3.4.3 Replacement Theorem
A transformation of an entire logical formula is logically different from a transformation of a part of a logical formula.
Replacement theorem
Write C[A] for a logical formula that contains the logical formula A several times.
Let C[B] be the result of replacing A in C[A] with the logical formula B.
In this case, if A and B are logical equivalences, then C[A] and C[B] are also logical equivalences.
The result of replacing a part of a formula with a logically equivalent formula is logically equivalent to the original formula.
Strong replacement theorem
(A→B)→(C[A]→C[B}) is a tautology
Longer syllogisms are allowed!
Λ can only be combined in two expressions at a time
Expressions of the form “AΛ(BΛC)” or “(AΛB)ΛC” can be formed as logical expressions, but
But a logical formula of the form “AΛBΛC” is not formed.
However, in the situation where we are focusing on the meaning (truth or falsity) of a formula, “AΛ(BΛC)” and “(AΛB)ΛC” are not distinguished.
Therefore, we allow “AΛBΛC” to be written.
Similarly, “AⅤBⅤC” is allowed.
Bad example
There is a difference between “(A→B)→C” and “A→(B→C)”.
Do not write like A→B→C

3.5 Reflecting on the Truth Table from a Theoretical Perspective

3.5.1 What was truth value analysis to do?
What is truth value analysis?
Based on truth value assignments to atomic formulas (e.g., 0 for P, 1 for Q, etc.)
(e.g., 1 for P→Q, 0 for PΛ(P→Q), and 1 for (PΛ(PΛQ)→Q).
Why such an extension is possible?
Because we have given the definition of the meaning of couplings in a form (diagram) that can be applied to any logical formula over and over again.
3.5.2 Truth-value assignment
Let us state the above story as it applies to any logical formula
Definition
Let F be a set consisting of L atomic formulas.
Let V, the truth assignment for F, be a function like the one above.
V is called the “valuation function”.
Generalized expression
Given a single truth assignment V to a set of atomic formulas F
From the atomic formulas contained in F, truth value assignments for the entire set of functionally defined logical formulas are derived from V.
Let Ḟ be the set consisting of all inductively defined logical formulas starting from the atomic formulas contained in F. Our goal is to extend the truth assignment V to F to obtain an extended version of the truth assignment Ṽ:Ḟ→[1,0] that assigns a 1 or 0 to each logical formula contained in this Ḟ
When we extend V to make Ṽ, we need to make it in a “consistent” way
The definition of “consistent way” is given by the definition of couplings
The expansion of truth assignments in logical expressions
It is important that the expansion of the truth assignment of a formula is parallel to the inductive definition of the formula.
Consistency of truth assignment
If we expand V to make Ṽ to satisfy the condition
Ṽ will always assign a truth value of either 0 or 1 to every possible logical formula.
Definition.
A truth assignment V to an atomic formula satisfies the logical formula A (or A is true under V, as the case may be)
⟺
V(A)=1

3.6 What is a Contradiction?

3.6.1 Defining Contradiction in a Set of Boolean Expressions
Given a collection of logical expressions, we cannot assign truth values to the expressions contained in it so arbitrarily.
Example
There is no truth value assignment that makes ¬P also true and ¬¬P also true
Is there any truth value assignment (to atomic formulas) that makes all four formulas (P, P→Q, ¬QⅤR, R→P) true at the same time?
There is no combination that makes all of them 1 at the same time
We say they are inconsistent.
Inconsistent” refers to a collection of logical formulas (a set of logical formulas)
From now on, we will use the Greek letters 𝜦, Θ, and 𝚺 to represent a set of logical expressions.
Definition of a contradiction in a logical formula
A set of logical formulas Γ is a contradiction
⇔
There is no truth-value assignment that makes all the logical expressions in Γ true at the same time.
When Γ is not contradictory
When there is at least one truth-value assignment V that makes all the logical expressions in Γ true at the same time
Infinite set of logical expressions
There are infinitely many logical formulas.
Some sets of logical expressions are infinite sets.
Example
The set of all logical expressions that can be created by negating P several times
The definitions of contradiction and satisfiability also apply to these infinite sets.
3.6.2 Knight and Knave
A logical puzzle called “Knight and knave
The knight always speaks honestly
A knave always lies.
You are walking down the street and you meet some people, are they knights or scoundrels?
Example
You met a and b. In response to your question, a said “yes”. To your question, a says, “I am a scoundrel, but b is a knight. Now, are a and b rogues or knights, respectively?
The proposition that a is a knight is A, and the proposition that b is a knight is B.
a says, “I am a rogue, but b is a knight.”
A ¬AΛB is not enough teeth
The truth value of the proposition “a says ‘P'”
The truth value of the proposition “a says ‘P'” depends on whether P is true or false and whether a is a knight or a scoundrel
Equivalent to “A⟷P

3.7 What is the correctness of an argument?

3.7.1 Counterexamples are the key to understanding the validity of an argument
The task of capturing the correctness of an argument
What does it mean for an argument to be correct?
Example
Teacher: If a2=1, how many is a?
Tomoya: If a=1, then a2=1
Teacher: there must be a=-1
Why does a=-1 show the ineffectiveness of the argument?
Both premises of the argument will be true, but the conclusion will be false
Definition.
A case in which all the premises of an argument are true, but the conclusion is false, is called a counterexample to the argument.
A valid argument is one in which there are no counterexamples.
3.7.2 Defining the Validity of an Argument
Truth table 1 of the above example
(gray area) Both premises are 1, but the conclusion is 0.
There is a counterexample, so this argument is not valid.
Definition
From premises A1,… ,The argument that leads to conclusion C from An is valid
⇔
A1,… , An, and C that simultaneously set A1,… An, and C that simultaneously set A1,…,An, and C to 1 and C to 0 (i.e., counterexamples) do not exist.
3.7.3 Proof by constructive double-edged argument and case separation
If we play like this, we lose (A→C) If we play like this, we lose (B→C) But we can only play like this or like this (AⅤB) ————————————————- Either way, we lose (C)
Either way, the result is the same.
<problem>.
Prove that there is a number of the form ab such that a and b are both irrational numbers but are rational numbers.
√2√2 is a rational number → There is a number in ab that is rational even though both a and b are irrational. √2√2 is an irrational number → There is a number in ab that is rational even though both a and b are irrational. √2√2 is a rational number Ⅴ √2√2 is a rational number ———————————– ————————————————————— Some ab are rational numbers even though both a and b are irrational numbers.
The possible cases are A1ⅤA2Ⅴ… There are n possible cases like VAn.
If we can say that the same C is true in all of these cases
If you can say that the same C is true in all of these cases, you can say that C is true without distinction.
3.7.4 The Mystery of “Anything Can Come Out of a Contradiction
If the soul exists, then modern science is wrong. Modern science is not wrong, the soul exists. ——————————————— The most sophisticated city in Japan is Nagoya.
According to the definition of validity of an argument, it is valid.
I tried to find a counterexample, but I couldn’t find one.
There is no such thing as a time when all premises are 1.
There is no case where all premises are 1 and 0 (i.e. counterexample)
An argument with contradictory premises will be valid no matter what comes to the conclusion.
Any conclusion can logically come from contradictory premises
3.7.5 The Three Faces of Logic are One
What relationship do the concepts of logical consequence, contradiction, and formal truth have to each other?
Argument Validity and Tautology
Theorem 9
From premises A1,… The argument that leads to conclusion C from premises A1,…, An is valid
⇔
logical formula (A1Λ…. .ΛAn) → C is a tautology
Validity and Logical Equivalence
Theorem 10
A and B are logically equivalent
⇔
Argument A/B and Argument B/A are both valid
We can also view the logical validity of two logical formulas as their logical consequence from each other
The three basic concepts <validity of an argument><contradiction of a set of logical formulas> and <tautology> are connected to each other.

3.8 The relationship of logical consequence

3.8.1 Defining logical consequence
Assumptions A1,… , that an argument with An and a conclusion C is valid is
A1,… C logically follows from A1,…,An. ,An)
C is a logical consequence of A1,…,An. C is a logical consequence of A1,…,An , An)
Once the concept of validity of an argument is defined
When the notion of validity of an argument is defined, the notion of “logical consequence” or “logical emergence” is also defined
If C is the logical consequence of A1,…,An , is a logical consequence of An
⊨ Double turnstile
Turnstile: A turnstile at an amusement park or train station.
Definition 1
A1,… ,An ⊨ C
⇔C
A1,… , An, and C, a truth value assignment that simultaneously sets A1,… There is no truth-value assignment that simultaneously sets A1,…, An, and C to 1 and sets C to 0.
Overall, we claim that there is a relationship between the set of logical formulas on the left side and the logical formulas on the right side.
We denote any set of logical formulas by Γ and redefine it as follows
Definition 2
Γ ⊨ C
⇔
Among the truth-value assignments to the formulas in Γ and all the atomic formulas that make up C (which we will simply call “atomic formulas in Γ and C”), there is no truth-value assignment that simultaneously sets all the formulas in Γ to 1 and C to 0.
Relationships between abstractly conceived logical formulas, independent of whether they are proved or not.
Promise of simplified notation
Expanded interpretation of double turn style
When Γ is the empty set
Definition
⊨ C ⇔ C is a tautology
If there is nothing on the right-hand side
Definition.
Γ ⊨ ⇔ Γ is a contradiction
3.8.2 Theorems about logical consequence relations
Principles related to structure
The following theorem holds for logical consequence relations
Theorem 14
A ⊨ A (i.e., any logical formula logically attributes itself to itself)
If Γ ⊨ A, then Γ, B ⊨ A
thining, monotonicity.
If A logically follows from Γ, then A still follows no matter what B is added to the premise.
If Γ ⊨ A, A, ∆ ⊨ B, then Γ, ∆ ⊨ B
called cutting.
The relation of logical consequence is transitive.
If B comes logically out of A (A⊨B) and C comes logically out of B (B⊨C), then C comes logically out of A (A⊨C)
Logic without monotonicity
Principle specific to each connective
Theorem 15.
A, ¬A⊨B
Anything can come out of a contradiction
Γ, ¬A⊨ ⇔ Γ⊨A Γ, A⊨ ⇔ Γ⊨¬A
If Γ and ¬A together are a contradiction, then A logically follows from Γ
Γ⊨AΛB ⇔ Γ⊨A and Γ⊨B
Γ, AⅤB⊨ ⇔ Γ, A⊨ and Γ, B⊨
Γ, A⊨B ⇔ Γ⊨A→B Translated with www.DeepL.com/Translator (free version)

3.9 The concept of truth functions

3.9.1 What is a truth function?
The Origin of the Problem
How many couplings do we need?
What do we get in trouble for if we reduce the number of couplings?
What would be good to do with more couplings?
What is a “00” and is it enough to do a “00”?
Truth functions
Function
N-Variable Functions
Direct product of sets
Truth table
P→Q itself represents a function that maps 0 to <1,1>, 0 to <1,0>, 1 to <0,1>, and 0 to <0,0>.
Similarly, ¬PΛQ represents another function
A logical expression can be regarded as representing a function from the direct product {1,0}2={<1,1>,<1,0>,<0,1>,<0,0>} of the truth set {1,0} to {1,0}.
3.9.2 How many truth functions are there?
One variable truth function
The total number is 22=4
f1-1 can be any tautology consisting of P
P V ¬P
P→P
The simplest logical formula for f1-2 is P
The rest are ¬¬P
The same truth function can be represented by many different logical formulas
Two variable truth functions
Total number is 24=16
Two-variable truth functions can be represented by all available couplings
N variable truth functions
For example, 3 variables
There are no conjunctions in natural language that can connect 3-variable truth functions (i.e., connect 3 sentences at once)
There are 28=256 ways
Three-place majority function
Always output the majority of the three incoming truth values.
Corresponding logical expression
Are the couplings introduced so far sufficient to represent all truth functions?
General Definition of Truth Function
Definition
A function from {1,0}n to {1,0} is called a truth function of n variables.
Mathematically, it is called a Boolean function.
Number of truth functions of n variables
22n
3.9.3 Representation theorems for truth functions
Theorem 17
Any truth function of n variables can be represented by a logical formula containing only ¬, Λ, and V as binders.
¬, Λ, and V are “adequate” or functionally complete.
Example
Notice that the output is 1, lines 3,7,8,12,16.
In line 3, P is 1, Q is 1, R is 0, S is 1
If we make a logical formula PΛQΛ¬RΛS, we get a logical formula where only the third line is 1 and the rest are 0.
In the seventh line, P is 1, Q is 0, R is 0, and S is 1.
If we create the logical formula PΛ¬QΛ¬RΛS, we get a logical formula where only the seventh line is 1 and the rest are 0.
Connect all the expressions that result in 1 with V
(PΛ¬QΛ¬RΛS)V(PΛ¬QΛ¬RΛS)V….
The result is a logical formula that produces the output of the truth table.
3.9.4 What combinations of connectives are sufficient?
Can the number of sufficient binder combinations be further reduced?
{¬,Λ}, {¬,V}, and {¬,→} are sufficient.
Combinations that are not sufficient (1)
<Theorem 18>.
A logical formula containing only binary couplings Λ, V, → and ⟷ cannot be a contradiction formula
Incomplete combinations (2)
It is wrong to say that a formula is complete if it contains ¬.
3.9.5 Schaeffer’s magic rod
A truth function of two variables with the above truth values
We write “|” and call it “nand” for a conjunction such that
A | B is the same as ¬(AΛB)
nand because it is a combination of not and and
At this time
¬P ⊨⫤ P|P
PΛQ ⊨⫤ ¬(P|Q) ⊨⫤ (P|Q)|(P|Q)
Λ and ¬ can be defined by|
Since {¬, Λ} is sufficient, { | } is also sufficient.
Any truth function can be expressed by { | }.
Schaefer function
Any truth function can be represented by { | }.
<Definition 19> The only two-variable Schafer functions are| and↓.
There are many 3-variable, 4-variable, … There are many Schafer functions for 3, 4, …
Example of a 3-variable Schafer function
3-variable Schafer function
Also expressed as (PⅤQ)→¬R in Boolean expressions
You can use # to represent |.

3.10 Japanese “ならば” and “→” in logic

3.10.1 Uncomfortable feelings about “→
The binding “→” corresponding to “ならば” is defined by a truth table that is 1011 from above.
A→B is defined as the same thing as ¬AⅤB or ¬(AΛ¬b).
These are just rough approximations of “if”.
If we try to understand “→” in terms of the Japanese word “ならば”, we get a phenomenon that does not fit our intuition
(1) The following forms are all tautologies
¬A→(A→B), B→(A→B), A→(¬A→B)
For example, if we read in “if”.
If not A, then A is B
No understanding
(2) When the first case is false, A→B is true regardless of the truth value of the second case.
The case where the first and second cases are both true is also strange enough.
Example
P “Benzene is insoluble in water.
Q: “Julia Roberts was the Academy’s Best Actress in 2000.
P and Q are both true, but P → Q is true
The crucial difference between “→” and “ならば
Japanese “ならば
It requires that there is a content connection between the previous and subsequent cases.
“→”
The content of the atomic formula is not the issue, only the combination of truth values.
For any A and B, (A→B) V (B→A) is a tautology
There is a sense of discomfort related to relevance.
3.10.2 Justifying the definition of “→”
Example
A babysitter’s child asked me to make an Evangelion.
(1) Switch to a plastic material (clay) to make it?
(2) Make a model with building blocks and convince her that it is the most similar.
Take the route of (2) and convince them that “→” is the most similar to “if” among truth functions.
Important features of “ならば
All the features of the Japanese “ならば” cannot be reflected in the truth-functional binding “→”.
Let’s pick up some of the features that Japanese “ならば” shows.
(1) The opposite is not necessarily true
The fact that “If A, then B” is true does not necessarily mean that “If B, then A” is true.
(2) Transitivity
If A is B and B is C, then A is C.” is true no matter what proposition comes to A, B, C.
Transitivity is also a formal truth for Japanese “ならば”.
The justification argument
In order to reflect these two in “→”, we can impose the following constraints
(1) A→B and B→A are not logical equivalences.
(2) (A→B)Λ(B→C))→(A→C) is a tautology
The problem was when the previous case was zero, so introduce α and β as above
In order to satisfy requirement (1), α must be equal to 1
To satisfy requirement (2), β must be equal to 1
Therefore, the result is 1011.

3.11 Compactness Theorem

3.11.1 What is the Compactness Theorem?
Theorem 20
The set of logical formulas Γ is satisfiable
⇔
Every finite subset of Γ is satisfiable.
When Γ is finite, it is natural (and becomes insignificant) to say “establish it in the trivial way”.
Even when Γ is an infinite set, the direction of ⇒ is established in the trivial way
This definition is only meaningful in the direction of ⇐ where Γ is an infinite set
When Γ contains an infinite number of expressions
When Γ contains infinitely many formulas, if any finite subset of Γ can find a truth assignment that satisfies each of them, then
we say that Γ is finitely satisfiable.
We don’t know what it looks like, but there is a truth assignment that satisfies the whole of Γ.
3.11.2 Proof of the Compactness Theorem, Part I
3.11.3 Proof of the Compactness Theorem, Part II

3.12 On Metalanguage and Target Language

3.12.1 Let’s distinguish between meta-language and target language
We should not mix the language L (e.g. Λ, ¬, ↔︎) with the expressions we use to say various things about the language L (e.g. ⊨⫤, ⇔).
L is the object language because it is the object of study.
P,Q,… P,Q,…,V,Λ,¬,→,…”
To study something, you have to use a language.
The language for talking about the properties of language L is called meta-language.
True, tautology, logical equivalence, logicians, connectives.
3.12.2 Semantically Closed Languages and Paradoxes
A language is said to be semantically closed if it can be used simultaneously as a target language and as a meta-language.
In a “semantically closed language,” a language can self-refer to itself in terms of earthquakes.
These self-references can play all sorts of tricks.
Typical examples
The semantic paradox
Liar paradox
“This sentence is false.
3.12.3 Tarski’s recent ideas on language hierarchy and the liar paradox
In order to avoid the liar’s paradox, the Polish logician Alfred Tarski decided to exclude semantically closed languages from consideration
The definition of truth and falsehood in L should be done by a meta-language different from L
Hierarchize the language
Criticism that the above approach was overkill
Was it necessary to forbid all self-reference?
Obviously there are plenty of self-references that do not create harmless paradoxes
Examples
Is this sentence a question?
This sentence is a Japanese sentence
Is the minute responsible for the liar’s paradox?
No self-reference is needed to create the liar’s paradox.
Examples
Postcard paradox
On the front “the other side says the wrong thing” and on the back “the other side says the right thing.
If you only take out the sentence that is written, it is not a paradox
Self-reference is not included.
Proposal by Saul Kripke
Watergate paradox
(1) Half of what Nixon said about Watergate is false.
(2) Everything Jones said about Watergate is true.
(2) Everything Jones did about Watergate is true. It was Jones who said (1). (2) Everything Jones said about Watergate is true.
It was Nixon who said (2). And other than this statement, Nixon’s statements about Watergate were just 50/50.
Whether or not it creates a paradox depends on the situation in which the statement is used.
It is not possible to distinguish between a statement that creates a paradox and one that does not.
It is not the sentence itself that is responsible for creating the liar’s paradox, but the sentence and the situation in which it is used.
It is possible to use a sentence that contains self-reference in a way that does not create a paradox.
Tarski’s idea of linguistic hierarchy excludes all such sentences.
In current logic
loosening the Tarskian language hierarchy.
The current focus in logic is on loosening the Tarski language hierarchy, and on how to avoid the liar paradox in a semantically closed language. Translated with www.DeepL.com/Translator (free version)

Chapter 4: Logic as a Machine
4.1 Methods of Semantic Tableau

4.1.1 Let’s create a mechanical decision procedure
If there is a decision procedure that judges important concepts of logic, such as validity, contradiction, and tautology, create it.
The procedure must be a mechanical procedure.
It should meet the following requirements
The procedure must be clear.
There must be a single operation to be performed next.
The result of that operation is also determined
The procedure must be generic.
What doesn’t work
Procedures that can be judged only by the validity of three premises
A procedure that judges only the tautology of a logical formula consisting only of “→”.
The procedure must be usable for any kind of argument or logical formula.
The procedure must be finite.
It doesn’t matter how long it takes, the execution of the procedure will eventually be completed after a number of steps.
The following two are different issues
Clearly defining what is meant by the notions of validity, inconsistency, etc.
Is there an algorithm to determine them?
Truth table is a good example
A truth table is not an easy algorithm to use.
The procedure for writing a truth table leaves no room for ingenuity or intuition.
Practical alternatives to truth tables
Truth tree
semantic tableau
4.1.2 The Roots of Tableau
What ideas are the methods of tableau based on?
Example
Is the set of expressions {¬(PΛQ), (PⅤQ)Λ¬Q} contradictory or satisfiable?
(1) Set all the logical expressions in this formula to 1 Seek to find a consistent truth assignment
If successful, it is satisfiable.
If not, it is inconsistent.
(2) Assume that ¬(PΛQ) and (PⅤQ)Λ¬Q are both 1.
(3) In order for (PⅤQ)Λ¬Q to be 1, PⅤQ must be 1 and ¬Q must be 1
(4) For ¬Q to be 1, Q must be 0
(5) In order for P V Q to be 1, either P or Q must be 1.
(6) If Q is 1, (4) does not match.
(7) Suppose P is 1.
(8) For (PⅤQ)Λ¬Q to be 1, either P or Q must be 0.
(9) P is 0 does not match (7)
(10)If ¬Q is 0, it contradicts (3)
(11) An attempt to assign a coherent truth-ground that sets both ¬(PΛQ) and (PⅤQ)Λ¬Q to 1 has failed.
4.1.3 Hints to make the method mechanical
(A) Illustrate the above example.
(B) A simplified schematic of the above example
(C) Further greening
Omit the part for =1
The =0 part is marked with ¬.
4.1.4 Making tableau a generic method
A diagram like (C) is called a “tableau”.
In a tableau (C), the initial single pathway branches off and eventually three paths are created.
Summarize the procedure for creating a tableau
Definition
A path is a set of formulas created by following a tableau from its top all the way to its end and collecting the logical formulas contained in it.
The left path
{¬(PΛ¬Q), (PⅤQ)Λ¬Q, PⅤQ, ¬Q, P, ¬P}
The middle path
{¬(PΛ¬Q), (PⅤQ)Λ¬Q, PⅤQ, ¬Q, P, ¬Q}
The right path
{¬(PΛ¬Q), (PⅤQ)Λ¬Q, PⅤQ, ¬Q, Q}
What did it mean to make a tableau?
In order to complete (C), we need to
(1) List the logical formulas contained in the first set of formulas to be checked.
(2) Make lines 3 and 4 from line 2.
When a pathway of the form “AΛB” appears, add A and B in a vertical line following the pathway
Rule “Λ”
(3) Make lines 3 through 5.
When an expression of the form “A V B” appears in the path, split the path into two and add A to one path and B to the other.
Rule “V”
(4) After extending to the fifth line, Q and ¬Q both appear in the right path.
If a certain logical formula and its negation appear together, then
The pathway that ended in failure
(5) The path on the left is {¬(PΛ¬Q), (PⅤQ)Λ¬Q, PⅤQ, ¬Q, P, ¬P}
It is still unknown if there is a truth assignment that satisfies this path.
Consider how to get ¬(PΛ¬Q) to be 1 in this path
Branch out to line 6
Rule “¬Λ”
(6) After applying the rule “¬Λ”, the path has three lines.
Expansion rule and judgment criteria
The above mentioned [Λ], [V], [X], [¬Λ], etc. are called “expansion rules”.
Expansion rules
Notes on assigning expansion rules
In order to apply these rules at each stage of the tableau construction
They must always be applied to the whole formula, and must be applied to the sub-logic formula
When applied to PΛ(QⅤR), it is [Λ] and not [V].
4.1.5 Closed Paths and Closed Tableaux
{P→Q, Q→P} is not a contradiction.
Multiply this expression set by the tableau
Put P→Q and Q→P in a vertical line, and apply “→” to P→Q. when you have already guessed.
Next, apply “→” to Q→P again.
There is no contradiction because there is still one without an X.
Closed path
Definition
A path with an X at the end is called a “closed pqth”, and a path without an X is called an “open path”.
Closed tableau
Whether or not all the paths in a tableau are closed is the criterion for determining inconsistency.
Definition
A tableau in which all the paths are closed is called a closed tableau, or the tableau ends up being closed. Conversely, a tableau that still has at least one open path after applying all the expansion rules is called an open tableau, or the tableau ends up being open. The tableau ends up being open.
Criteria for determining whether a set of logical expressions is inconsistent
If the set of logical expressions {A1,A2… ,An} is inconsistent
⇔
A1,A2,… ,An vertically aligned and started tableau becomes a closed tableau
4.1.6 Let’s draw a tableau in a human way — a strategy for tableau composition
There is a trick to the order in which the rules are applied.
Inefficient tableau
Efficient tableau (1)
Efficient tableau(2)
Strategy
Apply non-branching expansion rules first
In case of branching, apply expansion rules to rows where at least one of the paths is closed.
4.1.7 Judgment and tableau of validity, tautology, and logical equivalence
Derive conclusion C from premises A1, A2,… , the argument leading to conclusion C from An is valid
⇔
Formula set {A1,A2,… An, ¬C} is inconsistent.
The logical formula A is a tautology
⇔
{¬A} is a contradiction
From the relation that
Tableau can be used as a method of judging the validity of an argument or the tautology of a logical formula.
Judgment criteria
Draw conclusion C from premises A1,… The argument that leads to conclusion C from premises A1,…, An is valid.
⇔
A1,…. and An, and ¬C are vertically aligned to form a closed tableau.
The logical formula A is a tautology
⇔
The tableau starting from ¬A is a closed tableau Translated with www.DeepL.com/Translator (free version)

4.2 Reliability of Tabloid

4.2.1 Why should we check for reliability?
The method of tableau, viewed as a mechanical procedure, is a syntactic procedure that thoroughly ignores meaning.
Are such results reliable as judgments about semantic facts pertaining to the meaning of the symbol of contradiction?
To that end
First of all, check whether the decision ends in a finite number of steps (decidability).
Second, is it guaranteed that the result is always correct? is the result always guaranteed to be correct?
4.2.2 Decidability of tableau
Theorem 22
The method of tableau is decidable.
4.2.3 If a closed tableau occurs, it is a contradiction
Theorem 23.
A closed tableau arises from a finite set Γ of equations
⇔
Γ is a contradiction.
4.2.4 A contradictory set always gives rise to a closed tableau
Theorem 24.
A finite set Γ of equations is a contradiction
⇔
A closed tableau arises from Γ
contradiction
An open tableau arises from Γ
⇔
The set of expressions Γ is satisfiable.
If we say that for any open path there is always a truth assignment V that satisfies all the expressions contained in it, then since this V satisfies the open path, it also satisfies the starting point Γ.
If we say that from an open path we can construct a truth assignment that satisfies all the equations in it, then we can say that from an open path we can construct a truth assignment that satisfies all the equations in it.
The following is a rigorous proof that can be applied to any open path
Proof approach with “model set” or “Hintikka set
Hintikka set
Definition
A set ∆ of logical formulas satisfying the following conditions is called a Hintikka set
(¬): For any primitive formula P, both P and ¬P cannot belong to ∆.
(¬¬): ¬¬A ∈ ∆ ⇒ A ∈ ∆
(Λ): AΛB∈∆ ⇒ A∈∆ and B∈∆
(¬V): ¬(AⅤB)∈∆ ⇒ ¬A∈∆ and ¬B∈∆
(¬→): ¬(A→B) ∈ ∆ ⇒ A ∈ ∆ and ¬B ∈ ∆
(¬Λ): ¬(AΛB)∈∆ ⇒ ¬A∈∆ or ¬B∈∆
(V): A ⅤB ∈ ∆ ⇒ A ∈ ∆ or B ∈ ∆
(→): A→B∈∆ ⇒ ¬A∈∆ or B∈∆
(↔︎): A↔︎B∈∆ ⇒ (A∈∆ and B∈∆) or (¬A∈∆ and ¬B∈∆)
(¬↔︎): ¬(A↔︎B)∈∆ ⇒ (A∈∆ and ¬B∈∆) or (¬A∈∆ and B∈∆)
Satisfiability of Hinticka sets
Theorem 25.
Any Hinticka set is satisfiable
Proof that the open path of tableaux is satisfiability
We can prove that the open path of tableau is a Hinticka set

Summary of Part I

Goals of Logic
To clarify the notions of correctness of argument, contradiction, and logical truth
To create an artificial language L that is convenient to bring up the form
To achieve the above goals by studying the properties of the language.
To define L, we define the syntax.
Determine the vocabulary
Define the logical formula of L functionally.
Significance of defining logical formulas of L functionally
All possible logical expressions can be included in the target
By being created functionally from simpler forms of partial logical expressions
A technique for proving facts for all logical formulas
The generalization of connectives and truth functions can provide a quantum leap in everyday argumentation and reasoning.
The concept of truth functions in N variables is not found in natural language.
The structure of an infinite set of inductively defined logical formulas can be used as the basis for a truth function.
both in terms of syntax and semantic vinegar.
Moving away from natural language

In the next article, I will describe my reading notes in the second part.