Symbolic logic

Japanese: 記号論理学 - きごうろんりがく（英語表記）symbolic logic

Also known as mathematical logic, it is a branch of logic that represents propositions and logical concepts with symbols and reduces inference to formal laws, which are the transformation of equations. In the second half of the 19th century, G. Boole and others developed logical algebra, and Frege built the foundations of modern symbolic logic. B. A. W. Russell developed it further, culminating in Principia Mathematica (1910), and established the methodology of symbolic logic.

[Toshio Nishimura]

Symbols in Logic

A proposition is something that asserts something, such as "snow is white," "3 < a and a < 8," or "if n is any natural number, there exists a natural number m such that n < m." 3, a, 8, etc. are the objects that the proposition deals with, and "is snow," "white," "<," "is a natural number," etc. express the properties of the objects, and are called predicates or propositional functions. "And," "any," and "exist" are logical concepts that combine propositions. In symbolic logic, all of these things are represented by symbols. Objects include constants and variables, and symbols such as 1, 2, etc., or x, y, etc. are used, respectively. These symbols are collectively called terms. There are various styles of symbols (called logical symbols) that represent logical concepts that combine propositions, but here we will use ~ (negation), "∧" (logical AND), "∨" (logical OR), (implication), "∀" (universal quantifier), and "∃" (existence symbol). ～A, A∧B, A∨B, and A⇒B are read as "not A", "A and B", "A or B", and "if A then B", respectively. Furthermore, ∀xF and ∃xF are read as "F is true for all x" and "there exists an x for which F is true", respectively. ∀ and ∃ are collectively called quantifiers or binding symbols. Furthermore, symbols are used to represent primitive propositions and predicates that do not contain logical symbols. Predicates include those that contain only one term, such as N(x), and those that contain two terms, such as the "<" in x＜y. In general, a predicate that contains n terms is called an n-term predicate. A primitive proposition can also be considered a zero-term predicate. A proposition expressed as a symbol is called a logical formula, and is defined as follows: (1) A primitive proposition symbol is a logical formula. If R(t ₁ ,…, t n ) is an n-ary predicate and t 1 ,…, t _n are terms, then R(t ₁ ,…, t _n ) is a logical formula. These are called prime logical formulas. (2) If A and B are logical formulas, then ~A, A∨B, A∧B, and A⇒B are also logical formulas. (3) Suppose F is a logical formula that does not contain ∀x or ∃x with variable x. In this case, ∀xF and ∃xF are logical formulas. In this way, variables that appear with ∀ or ∃ are called bound variables, and variables that do not are called free variables.

[Toshio Nishimura]

The meaning of symbols in symbolic logic

The logic commonly used in mathematical proofs is called two-valued logic, in which a proposition (logical formula) is considered to take on only one value: "true" (represented by 1) or "false" (represented by 0). The "true" or "false" value of a proposition is called its truth value.

[Toshio Nishimura]

Propositional logic and predicate logic

Within symbolic logic, the area that focuses on and studies only the logical symbols ~, <, >, and ⇒ is called propositional logic, while the general case that includes the quantifiers ∀ and ∃ is called predicate logic. In propositional logic, the following formulas hold. "=" means that no matter what values you put for A, B, and C in the formula, whether 1 or 0, the left and right sides will always have the same value.

(1)A∨~A=1 (excluded middle law), A∨0=A
(2) A∨A＝A (absorption law)
(3) A∨B＝B∨A (commutative law)
(4)(A∨B)∨C＝A∨(B∨C) (association law)
(5)A∧(B∨C)＝(A∧B)∨(A∧C)(distribution law)
(6) ~(A∨B)=~A∧~B (De Morgan's Law)
(1)′A∧～A=0 (law of contradiction), A∧1=A
(2)′A∧A＝A
(3)′A∧B＝B∧A
(4)′(A∧B)∧C＝A∧(B∧C)
(5)′A∨(B∧C)＝(A∨B)∧(A∨C)
(6)′〜(A∧B)＝〜A∨〜B
(1)'~(6)' are the results of replacing ∧, ∨, 1, and 0 in (1)~(6) with ∨, ∧, 0, and 1, respectively. This is called the principle of duality. If ∧, ∨, and ~ are the operations of "production," "addition," and "complement" in Boolean algebra, respectively, and 1 and 0 are taken as the maximum and minimum elements, respectively, it can be seen that the entire set of logical formulas in propositional logic constitutes Boolean algebra. Furthermore, if we use these formulas to transform a logical formula, we can transform it into one that contains only ~ and ∧, or ~ and ∨, or ~ and ⇒. Furthermore, if A|B (called Schaefer's rod) is taken to mean ~(A∧B), then all other logical symbols can be defined using only A|B. A∨~A has the value 1 whether A is 1 or 0. A logical formula is said to be "identically true" or a tautology if the value 1 or 0 is given to the elementary formulas contained within it and the formula always has the value 1. In propositional logic, there is a way to verify whether a logical formula is identically true. Between the logical formulas ∀xF and ∃xF in predicate logic,
～∀xF＝∃x～F, ～∃xF＝∀x～F
Therefore, we can define ∃ by using ~ and ∀, and ∀ by using ~ and ∃. The formula ∀x(F∨~F) in predicate logic is identically true, but there is no general method to verify whether any formula in predicate logic is identically true.

[Toshio Nishimura]

Axiomatic development of symbolic logic

Symbolic logic can also be developed axiomatically. There are various ways to choose the axioms and inferences, but one way is to first give the following axioms.

(1)(A⇒B)⇒((B⇒C)⇒(A⇒C))
(2) (～A⇒A)⇒A
(3) A⇒(～A⇒B)
where A, B, and C are any logical expressions.

(4) When x is a variable not included in A,
∀x(A⇒B)(A⇒∀xB)
(5)∀xA⇒A′
Here, A' is a logical formula obtained by replacing all variables x that appear in A with a variable that is not included in A as a bound variable, or with a constant y.

The following two inference rules are given:

(1) B is derived from A and A|B (syllogism).

(2) When x is a variable, we obtain ∀xA from A. Propositional logic consists only of axioms (1), (2), and (3) and inference rule (1), while predicate logic consists of the whole. A formula A is proven when A is obtained by applying the inference rules one after another from the axioms. In the system of predicate logic, all formulas that are proven are identically true, and there is no formula A in which both A and ~A are proven. This is called consistency. Also, a formula that is identically true can always be proven. This is called completeness. The system of predicate logic is consistent and complete. Therefore, in both propositional logic and predicate logic, a formula is identically true and can be proven. Providing a general method for verifying whether any formula A can be proven is called a decision problem. In propositional logic, a decision problem can be solved affirmatively, but in predicate logic, it can be solved negatively.

What has been said so far is that propositions can take the values "true" or "false" and are governed by the law of the excluded middle (there are no other values than true and false). This is also called classical logic. There is also symbolic logic that expands the domain of classical logic to include "sets," "sets of sets," etc. This is called higher-order predicate logic. There is also research into intuitionistic logic, which symbolizes the reasoning used in "intuitionistic mathematics," which does not recognize the law of the excluded middle. There is also research into three-valued logic, which has a third truth value in addition to truth and false, and multi-valued logic, which has more truth values. There is also research into modal logic, which has logical operations to express modal propositions that express possibility and necessity within symbolic logic.

[Toshio Nishimura]

"Introduction to Symbolic Logic" by Shoji Maehara (1967, Nippon Hyoronsha) " "Mathematical Logic" by Kazuo Matsumoto (1971, Kyoritsu Shuppan)

[References] | Boolean algebra | Propositions [Additional information] | Truth values in two-valued logic

Truth values in binary logic (table)
©Shogakukan ">

Truth values in binary logic (table)

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

Japanese:

数理論理学ともいう。命題や論理概念を記号で表し、推論を式の変形という形式的な法則に還元して論理学を組織する一分科である。19世紀後半にG・ブールらの論理代数が現れ、フレーゲによって現代の記号論理学の基礎が築かれた。B・A・W・ラッセルはこれを大きく発展させ、『プリンキピア・マテマティカ』Principia Mathematica（1910）に集大成し、記号論理学の方法を確立した。

［西村敏男］

記号論理学における記号

「雪は白い」「3＜aかつa＜8」、あるいは「nを任意の自然数とするとき、n＜mとなるような自然数mが存在する」のように、ある一つの主張をしているものが命題である。3、a、8などは命題が扱う対象で、「雪である」「白い」「＜」「自然数である」などは、対象のもつ性質を表し、述語とか命題関数といわれる。「かつ」「任意の」「存在する」は命題を合成する論理概念である。記号論理学ではこれらのものをすべて記号で表す。対象には定数と変数があり、それぞれ1、2など、あるいはx、yなどの記号を用いる。これらの記号を総称して項とよぶことにする。命題を合成する論理概念を表す記号（論理記号という）としては、いろいろの流儀のものがあるが、ここでは～（否定）、「∧」（論理積）、「∨」（論理和）、（含意）、「∀」（全称記号）、「∃」（存在記号）を用いる。～A、A∧B、A∨B、A⇒Bをそれぞれ「Aでない」「AかつB」「AあるいはB」「AならばB」と読む。また∀xF、∃xFはそれぞれ「すべてのxについてFが成り立つ」「Fが成り立つようなxが存在する」と読む。∀と∃を総称して限定記号とか束縛記号ともいう。さらに、論理記号を含まない原始命題や述語を表す記号を用いる。述語にはN(x)のように項を一つしか含まないものや、x＜yの「＜」のように、二つの項を含むものなどがある。一般に、n個の項を、含む述語をn項述語という。原始命題はゼロ項述語とも考えられる。命題を記号で表したものを論理式といい、次のように定義する。(1)原始命題記号は論理式である。R(　,…,　)がn項述語で、t₁,…, t_nが項であれば、R(t₁,…, t_n)は論理式である。これらを素論理式という。(2)AとBが論理式であれば、～A、A∨B、A∧B、A⇒Bもまた論理式である。(3)Fが論理式であり、このなかには、変数xを伴った∀x、∃xは含まれていないとする。このとき、∀xF、∃xFは論理式である。このように、∀や∃を伴って現れる変数を束縛変数、そうでない変数を自由変数という。

［西村敏男］

記号論理学における記号の意味

数学の証明などで通常使われる論理を二値論理といい、命題（論理式）は「真」（1で表す）か「偽」（0で表す）のいずれか一方の値をとるものと考える。命題の「真」「偽」の値をその真理値という。

［西村敏男］

命題論理と述語論理

記号論理のうちで、論理記号～、＜、＞、⇒だけに着目して研究する範囲を命題論理とよび、限定記号∀と∃をも含めた一般の場合を述語論理という。命題論理では次の諸式が成り立つ。「＝」は、式のなかのA、B、Cに1と0のいかなる値を入れても、つねに左辺と右辺が等しい値をもつという意味である。

(1)A∨～A＝1(排中律), A∨0=A
(2)A∨A＝A(吸収律)
(3)A∨B＝B∨A(交換律)
(4)(A∨B)∨C＝A∨(B∨C)(結合律)
(5)A∧(B∨C)＝(A∧B)∨(A∧C)(分配律)
(6)～(A∨B)＝～A∧～B(ド・モルガンの法則)
(1)′A∧～A＝0(矛盾律), A∧1=A
(2)′A∧A＝A
(3)′A∧B＝B∧A
(4)′(A∧B)∧C＝A∧(B∧C)
(5)′A∨(B∧C)＝(A∨B)∧(A∨C)
(6)′～(A∧B)＝～A∨～B
　(1)′～(6)′は、(1)～(6)の∧、∨、1、0をそれぞれ∨、∧、0、1に一斉に置き換えたものである。これを双対の原理(そうついのげんり)という。∧、∨、～をそれぞれブール代数の「積」「和」「補元」の演算とし、1、0をそれぞれ最大元、最小元にとれば、命題論理の論理式の全体がブール代数をなすことがわかる。また、これらの式を用いて論理式を変形すれば、論理式は、～と∧、あるいは～と∨、あるいは～と⇒のみを含むものに変形できる。また、A|B（シェーファーの棒という）を～(A∧B)のこととすると、A|Bだけで他の論理記号がすべて定義できる。A∨～Aは、Aが1でも0でも値1をもつ。論理式は、そこに含まれる素論理式に任意に値1、0を与えるとつねに値1をもつとき、その論理式は「恒等的に真」な論理式、あるいは同語反復（トートロジー）という。命題論理では、論理式が恒等的に真であるかどうかを確かめる方法がある。述語論理の論理式∀xFと∃xFの間には、
　　～∀xF＝∃x～F, ～∃xF＝∀x～F
という関係がある。したがって、～と∀を用いれば∃を、～と∃を用いれば∀を定義することができる。述語論理の論理式∀x(F∨～F)は恒等的に真であるが、述語論理の任意の論理式に対して、それが恒等的に真であるかどうかを確かめるような一般的な方法はない。

［西村敏男］

記号論理の公理的展開

記号論理を公理的に展開することもできる。公理と推論の選び方にはいろいろのものがあるが、その一つとしてまず、次の公理を与える。

(1)(A⇒B)⇒((B⇒C)⇒(A⇒C))
(2)(～A⇒A)⇒A
(3)A⇒(～A⇒B)
ここでA、B、Cは任意の論理式である。

(4)xがAのなかに含まれない変数のとき、
　　∀x(A⇒B)(A⇒∀xB)
(5)∀xA⇒A′
ここでA′は、Aに現れる変数xをすべて、Aのなかに束縛変数として含まれていない変数、あるいは定数yで置き換えて得られる論理式である。

　推論規則として、次の二つを与える。

(1)AとA|BからBを得る（三段論法）。

(2)xを変数とするとき、Aから∀xAを得る。公理(1)、(2)、(3)と推論規則(1)だけからなるものが命題論理で、全体からなるものが述語論理である。論理式Aが証明されるというのは、公理から推論規則を次々と適用してAが得られることである。述語論理の体系では、証明される論理式はすべて恒等的に真であり、Aと～Aがともに証明されるような論理式Aは存在しない。これを無矛盾という。また、恒等的に真な論理式はかならず証明できる。これを完全性という。述語論理の体系は無矛盾でかつ完全である。したがって、命題論理でも述語論理でも、論理式が恒等的に真であることと、その論理式が証明できることは同じ意味である。任意の論理式Aが証明できるかどうかを確かめる一般的方法を与えることを決定問題という。命題論理では決定問題は肯定的に解けるが、述語論理では否定的に解ける。

　いままで述べてきたのは、命題は「真」か「偽」かの値をとり、排中律（真と偽以外の値はない）の成り立つものである。これを古典論理ともいう。古典論理の対象領域を、「集合」「集合の集合」……にまで広げた記号論理もある。これを高階の述語論理という。また、排中律を認めない「直観主義の数学」に用いられる論法を記号化した直観主義論理の研究もある。また、真偽のほかに、第三の値を真理値としてもつ三値論理、より多くの真理値をもつ多値論理の研究もある。さらに、可能性、必然性を表す様相命題を記号論理のなかで表現するための論理演算をもつ様相論理なども研究されている。

［西村敏男］

『前原昭二著『記号論理入門』（1967・日本評論社）』▽『松本和夫著『数理論理学』（1971・共立出版）』

[参照項目] | ブール代数 | 命題[補完資料] | 二値論理における真理値

二値論理における真理値〔表〕

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例

<<: Scandal (English spelling)

>>: Climate elements - climatic conditions