Syntax of L_FP

The syntax of fuzzy-annotated propositional logic extends the one of propositional logic in a very straightforward way. Let P be the (infinite) set of all propositions. If φ is a propositional logic formula (as defined in the first year booklet using propositions in P and symbols in {(, ), ¬, ∧, ∨, →}), and v ∈ [0,1] is a real number between 0 and 1, then φ : v is a formula in L_FP, and there is no other kind of formulas. To better distinguish formulas, they are always on a gray background.

(A ∨ B) ∧ (B ∨ ¬C) → D : 0.7

Semantics of L_FP

In fuzzy logic and fuzzy set theory, the numeric value indicates a degree of truth. It must not be confused with a probability. A formula “The room is loud” : 0.6 does not mean that there is 60 % chance that the room is loud (and therefore 40 % chance that it is not loud). Instead, it means that the room is at least a bit loud. Intuitively, the number given indicates a minimal amount of truth, so the fuzzy-annotated formula indicates that the room may be quite loud, or very loud, or more. At value 1, the statement would be considered entirely true (the room is 100 % loud) and at value 0, the room could be considered not loud or 50 % loud, or 100 % loud, as it has to be interpreted as a minimum. The interpretation of non atomic formulas involves calculations. We formalise this below.

An interpretation in L_FP is a function 𝓘 : P ⟶ [0,1].

We extend function 𝓘 to a function 𝓘̃ that assigns a value in [0,1] to all formulas of propositional logic as follows:

• for all A ∈ P, 𝓘̃(A) = 𝓘(A);
• for all propositional logic formula φ, 𝓘̃(¬φ) = 1 – 𝓘̃(φ);
• for all propositional logic formulas φ and ψ, 𝓘̃(φ ∧ ψ) = min(𝓘̃(φ),𝓘̃(ψ));
• for all propositional logic formulas φ and ψ, 𝓘̃(φ ∨ ψ) = max(𝓘̃(φ),𝓘̃(ψ));

An interpretation 𝓘 satisfies a formula φ : v in L_FP (written 𝓘 ⊨_FP φ : v) if and only if 𝓘̃(φ) ≥ v.

An interpretation could assign value 0.7 to proposition A = “It is raining” (it is raining a little but not completely), and value 0.5 to proposition B = “It is windy” (there is wind but not much). Then, this interpretation would satisfy the formula A ∧ B : 0.4, but would not satisfy the formula ¬A ∨ B : 0.6.

Given a set Φ of formulas in L_FP, if 𝓘 ⊨_FP φ : v for all φ : v ∈ Φ, then 𝓘 is called a L_FP-model of Φ.

Questions on L_FP

Question 1

What is the formal definition of entailment in L_FP, i.e., when a formula φ : v logically follows from a set of formulas Φ?

Answer 1

The formal definition of entailment is the same for all logics defined with a notion of interpretation and satisfaction: A set Φ of formulas L_FP-entails a formula φ : v if and only if all L_FP-models of Φ L_FP-satisfy φ : v.

Question 2

What is the definition of consistency (synonym of satisfiability) in L_FP?

Answer 2

The formal definition of consistency is the same for all logics defined with a notion of interpretation and satisfaction: A set Φ of formulas is L_FP-consistent if and only if there exists a L_FP-model of Φ.

Question 3

In the definition of 𝓘̃, we did not define 𝓘̃(φ → ψ). Using the well known equivalences of propositional logic, give the value of 𝓘̃(φ → ψ) in function of 𝓘̃(φ) and 𝓘̃(ψ).

Answer 3

We know that φ → ψ is equivalent to ¬φ ∨ ψ. Thus, we successively apply the formula for ∨ and for ¬: 𝓘̃(φ → ψ) = max(𝓘̃(¬φ),𝓘̃(ψ)) = max(1 – 𝓘̃(φ),𝓘̃(ψ)).

Question 4

Consider the following theory (that is, a set of formulas) in L_FP: T = {A : 0.5, B : 0.2, B ∨ ¬A : 0.6}, where A and B are propositions. Propose an interpretation that is a model of theory T in logic L_FP. You do not need to provide the proof that it is a model.

Answer 4

To have a model of the given theory, we only need to define the interpretation of propositions A and B. We define 𝓘_q4 such that 𝓘_q4(A) = 0.5 and 𝓘_q4(B) = 0.6. 𝓘̃_q4(A) ≥ 0.5 so 𝓘_q4 satisfies A : 0.5; 𝓘̃_q4(B) ≥ 0.2 so 𝓘_q4 satisfies B : 0.2; 𝓘̃_q4(B ∨ ¬A) = max(𝓘̃_q4(B),1 – 𝓘̃_q4(A)) = max(0.6,0.5) = 0.6. So 𝓘̃_q4(B ∨ ¬A) ≥ 0.6 so 𝓘_q4 satisfies B ∨ ¬A : 0.6. Therefore, 𝓘_q4 is a model of T.

Syntax

Let us consider an infinite set P whose elements will be called propositions. The set of symbols of L_⊕ is P ∪ {[, ], ⊕}. We will use the italicised upper case latin alphabet to denote propositions: A, B, C, etc.

The set of formulas in L_⊕ is defined as follows:

• all propositions A ∈ P are formulas A in L_⊕;
• for all formulas φ and ψ in L_⊕, [φ ⊕ ψ] is a formula in L_⊕;
• There is no other kind of formulas.

[A ⊕ [[B ⊕ A] ⊕ C]]

Semantics of L_⊕

An interpretation in L_⊕ is a function 𝓘 : P ⟶ {⊥, ⊤}.

An interpretation 𝓘 satisfies a formula φ in L_⊕ (written 𝓘 ⊨_⊕ φ) when:

• there is a proposition A ∈ P such that φ = A, and 𝓘(A) = ⊤, or
• there is a formula ψ₁ and a formula ψ₂ in L_⊕ such that φ = [ψ₁ ⊕ ψ₂], and 𝓘 does not satisfy ψ₁ or 𝓘 does not satisfy ψ₂ or 𝓘 neither satisfies ψ₁ nor ψ₂.

Given a set Φ of formulas in L_⊕, if 𝓘 ⊨_⊕ φ for all φ ∈ Φ, then 𝓘 is called a L_⊕-model of Φ. In digital electronics, the operator ⊕ corresponds to a NAND gate.

If we consider 𝓘 such that 𝓘(A) = 𝓘(B) = 𝓘(C) = ⊤, then 𝓘 satisfies A and B, so it does not satisfy [B ⊕ A], and consequently, 𝓘 satisfies [[B ⊕ A] ⊕ C]. As a result, the formula from the example above would not be satisfied by 𝓘. However, if instead 𝓘(A) = ⊥, then 𝓘 would satisfy the formula.

Questions on L_⊕

Question 5

The semantics of the operator ⊕ can be represented with a truth table that looks like so:

φ	ψ	[φ ⊕ ψ]
⊥	⊥	⊤
⊥	⊤	⊤
⊤	⊥	⊤
⊤	⊤	⊥

Fill in the table with truth values accordingly.

Question 6

Let us assume that proposition A means “It is raining”. Write a formula using A and the language of L_⊕ that expresses that “It is not raining”. You must only use a formula that is strictly in L_⊕ and nothing else (e.g., you are not allowed to write a propositional logic formula or a first order logic formula, and of course, the symbol ¬ is forbidden).

Answer 6

[A ⊕ A]

Question 7

Provide an example of a tautology in L_⊕.

Answer 7

For any proposition A, [[A ⊕ A] ⊕ A] is a tautology.

Question 8

If A means “It is raining” and B means “It is windy”, write a formula in L_⊕ that means “It is raining and windy”. Of course, symbol ∧ is not part of the logic L_⊕.

Answer 8

[[A ⊕ B] ⊕ [A ⊕ B]]

Question 9

If A means “It is raining” and B means “It is windy”, write a formula in L_⊕ that means “It is raining or windy, or both”. Of course, symbol ∨ is not part of the logic L_⊕.

Answer 9

[[A ⊕ A] ⊕ [B ⊕ B]]

Question 10

Assuming you could answer Questions 6 to 9, what can you say about L_⊕ compared to propositional logic? Can propositional logic express statements that L_⊕ cannot? Can L_⊕ express statements that propositional logic cannot express?

Answer 10

By definition of L_⊕, we can state atomic propositions. Using the construction of Question 6, we can express negation of any formula in L_⊕. Using Questions 8 and 9, we can express conjunction and disjunction of any formulas in L_⊕. This is sufficient to express all statements that are expressible in propositional logic. Conversely, it is easy to see that any formula [φ ⊕ ψ] can be expressed in propositional logic because any proposition is a formula in propositional logic, and if we can translate φ and ψ into propositional formulas φ̃ and ψ̃, then [φ ⊕ ψ] is equivalent to ¬(φ̃ ∧ ψ̃). So L_⊕ is not more expressive than propositional logic. In fact, L_⊕ and propositional logic are strictly equivalent, even though they are different logics.