常用到正規(正式/形式)演繹系統(formal deductive system)
以解決自然語言, 如英文, 無法直接程式化的問題
- An infinite set of variables, often denoted by lowercase letters at the end of the alphabet x, y, z,... .
- Symbols denoting logical operators (or connectives):
- The unary operator (logical not).
- Binary operators (logical and) and (logical or).
- Binary operators (logical conditional) and (logical biconditional).
- Symbols denoting quantifiers: (universal quantification, typically read as "for all") and (existential quantification, typically read as "there exists").
- Left and right parenthesis: ( and ). There are many different conventions about where to put parentheses; for example, one might write x or (x). Sometimes one uses colons or full stops instead of parentheses to make formulas unambiguous. One interesting but rather unusual convention is "Polish notation", where one omits all parentheses, and writes , , and so on in front of their arguments rather than between them. Polish notation is compact and elegant, but rare because it is hard for humans to read it.
- An identity symbol (or equality symbol) =. Syntactically it behaves like a binary predicate.
First-order logic as described here is often called first-order logic with identity, because of the presence of an identity symbol = with special semantics. In first-order logic without identity this symbol is omitted.
There are numerous minor variations that may define additional logical symbols:
- Sometimes the truth constants T for "true" and F for "false" are included. Without any such logical operators of valence 0 it is not possible to express these two constants otherwise without using quantifiers.
- Sometimes the Sheffer stroke (P | Q, aka NAND) is included as a logical symbol.
- The exclusive-or operator "xor" is another logical connective that can occur as a logical symbol.
- Sometimes it is useful to say that "P(x) holds for exactly one x", which can be expressed as x P(x). This notation, called uniqueness quantification, may be taken to abbreviate a formula such as x (P(x) y (P(y) (x = y))).
Not all logical symbols as defined above need occur. For example:
- Since ( x)φ can be expressed as (( x)( φ)), and ( x)φ can be expressed as (( x)( φ)), one of the two quantifiers and can be dropped.
- Since φψ can be expressed as (( φ) ( ψ)), and φψ can be expressed as (( φ) ( ψ)), either or can be dropped. In other words, it is sufficient to have or as the only logical connectives among the logical symbols.
- Similarly, it is sufficient to have or just the Sheffer stroke as the only logical connectives.
There are also some frequently used variants of notation:
- Some books and papers use the notation φ ψ for φ ψ. This is especially common in proof theory where is easily confused with the sequent arrow.
- ~φ is sometimes used for φ, φ & ψ for φ ψ.
- There is a wealth of alternative notations for quantifiers; e.g., x φ may be written as (x)φ. This latter notation is common in texts on recursion theory."
以上"Logical symbols及其變化"轉貼剪輯自(版權): http://en.wikipedia.org/wiki/First-order_logic (retrieved 11/16)