31

What is the difference between the implication/conditional truth function and the notion of logical entailment?

My naive understanding as a computer programmer is that the conditional is a function on two Boolean inputs, whereas entailment is some sort of more abstract idea about consequence.

Anything that's a thought or reference is deeply appreciated.

user
  • 467
  • 1
  • 4
  • 8

1 Answers1

23

The conditional/implication (→), as you said, is a function on statements/propositions (sentences that can be true or false). Consequence/entailment (⊨) is a relation between sets of statements and a statement. From the classical bivalent point of view, the distinction can be characterized as follows:

Implication. (φ → ψ) is true iff (¬φ ∨ ψ) is true.

That's the classical view of →. To evaluate (φ → ψ), it will suffice to evaluate φ, check its value: if the value is false, short-circuit and output true as the value of the whole thing; if the value is true, continue and evaluate ψ and output the value of ψ as the value of the whole thing.

Entailment. (Γ ⊨ ψ) is true iff every interpretation that makes all φ ∈ Γ true, makes ψ true.

That's the classical view of ⊨. To evaluate (Γ ⊨ ψ), it will suffice to consider an arbitrary interpretation of the logical symbols of the underlying language that makes all statements in Γ true, and check whether that (arbitrary) interpretation also makes ψ true. In some logic textbooks they phrase that same thing by saying that: ψ is a logical consequence of Γ just in case it's impossible to make all of Γ true and ψ false.

The characterization of each of these relations depends on the underlying logic. The classical view of both is significantly different from the views of intuitionistic, paraconsistent, relevantist, and other logics. Those SEP articles will introduce you to those perspectives and talk about their motivations.

Stop Slandering Monica Cellio
  • 103
  • 2
Hunan Rostomyan
  • 5,396
  • 3
  • 26
  • 40
  • OK cool that helped a lot. So would it be correct to say that: IF I have a function P(x,y,x) and another one Q(x,y,z), both of which return Booleans, and whenever P() returns true then Q() returns true; THEN P entails Q, at least inside the computer the functions are running on? – user May 30 '14 at 07:32
  • 1
    @bryanj The symbols are a little messed up, but yes, that's correct. Btw, sorry the SEP is down right now; this doesn't happen often. The articles are wonderful; you'll see when the server comes back up. – Hunan Rostomyan May 30 '14 at 07:35
  • I guess I made up my own symbols. How would one typically write the gist of my previous comment? – user May 30 '14 at 07:43
  • 1
    @bryanj There would be a convention of using P,Q,R,... for boolean-valued functions (aka 'predicates'). Then we would say that n-ary predicate P entails n-ary predicate Q iff all assignments a0,...,an-1 that make P true make Q true. Admittedly not precise, but in the abstract it's hard to do it more justice. If you have specific things you want to formalize in the future, we'll try to be more careful. – Hunan Rostomyan May 30 '14 at 07:54
  • 1
    OK I got it for predicates with a countable number of arguments. I don't expect to need any more than that for a very long time. But if I did... – user May 30 '14 at 08:00
  • One more thing (and I feel *really stupid* for asking this): I feel like I'm using something like *entailment* in order to define entailment as above. Am I missing something here? – user May 30 '14 at 08:04
  • 1
    @bryanj You're welcome to use 'entail' to mean either the arrow or the turnstile, but make sure you're not confusing them. In this classical setting, the two are very similar, so I think while what you said was a bit confused, because I knew what you were trying to say, I made the right disambiguations. (The issue is not just the arrow/turnstile difference; there are also lots of conventions about what sentences are, what sentential matrices/forms are, what connectives are, and so on. In logic everything depends on the language, so we'll try to get clear on these issues when proving things.) – Hunan Rostomyan May 30 '14 at 08:10
  • I guess my confusion with entailment boils down to this: Suppose a sentence A entails B, and B entails C. How can I know that in fact A entails C without "taking a step back" and abstracting *just a bit more*? – user May 30 '14 at 08:18
  • 1
    @bryanj Let FV(x) be the number of free variables in sentence x. To check whether A entails B and vice versa, it will be necessary and sufficient to do this. Take the union of FV(A) and FV(B), name it k. That gives you the list k of all free variables either in A or B. Now, since each proposition is either true/false, consider a truth-table with 2^|k| rows. Each of those rows assigns T/F to all the variables in k, so each row determines values for both A and B. If A and B entail each other, their main columns will have identical true/false values. – Hunan Rostomyan May 30 '14 at 08:24
  • You can think of each row as a binary number of length |k|. For example, let A = "if x then y" and B = "if y then x". FV(A) = x,y and FV(B) = x,y, and so k = x,y. The size of k is 2, so we have 4 rows. Those rows can be thought of as the binary numbers 00, 01, 10, and 11. Each of those numbers determines the value of A,B. For example, 00 |= A and 00 |= B, since A and B are true when either x or y are false and x and y are false according to 00. And so on. I'm not sure if the binary number idea is useful to you, but when I implement logic in software I use those instead of truth-assignments. – Hunan Rostomyan May 30 '14 at 08:29
  • I think I get the main idea. I will think about it, and slowly digest it over a period of 1000 years. I very much appreciate your help! – user May 30 '14 at 08:31
  • haha, it shouldn't take that long (unless that's in base 2; jk, it's still a long time). Glad to have been helpful. I'm falling asleep. I'll revaluate things tomorrow and get back to you if I find a dangerous mistake in what I've said tonight. – Hunan Rostomyan May 30 '14 at 08:34
  • 3
    @bryanj - Hunan's explanation of the difference between the *conditional* connective (→) and the *entailment* relation (|=) is perfect. They are very very different... But, in *classical* logic, we have the following result : |= A → B **iff** A |= B, which builds a "strong" bridge between the two and (sometimes) can cause the confusion of thinking that they are the "same thing", which is not correct from a "conceptual" point of view, and also taking into account the existence of other "logics" which are not "truth-functional". – Mauro ALLEGRANZA May 30 '14 at 09:30
  • 1
    Its worth saying, I think, that the first example is classical logic; and the second is model-theoretic - a development from the early 20C. – Mozibur Ullah May 30 '14 at 15:25
  • 1
    Just a minor note: Hunan's definition of logical consequence is NOT confined to the 'classical view', at least if what is meant by that is classical logic. Rather the definition merely says that consequence is model preservation, where a model of some set of sentences is an interpretation that verifies all of its elements. But you can have that notion without spelling out interpretations and truth in an interpretation in classical ways. That's exactly what happens in the various non-classical logics. – sequitur May 31 '14 at 11:28
  • @sequitur Yes. In the consequence case I'm calling "classical" the Tarskian conception of logical consequence. No commitment to classical laws is intended. Thank you both for the notes. – Hunan Rostomyan May 31 '14 at 17:20