Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
17

Is not exhaustive either, since there are actually 16 possible compound statements (and corresponding logical connectives) to choose from. (Since {¬,∨,∧,⇒,⇔} is already redundant, why not throw in the other 11 connectives, some of which are VERY helpful like "nand" ⊼ , "nor" ⊽ and "exclusive or" ⊻?) Some of the "16 possible compound statements" are in fact ...


10

It is true that : (Q≡⊤) ⊨ (P∧Q≡P) we can check it with a truth-table. But the other "direction" does not hold : when P and Q are both false, we have that (P∧Q≡P) is true but (Q≡⊤) is not.


10

There seem to be several overlapping concerns in your issue with proof by contradiction. You have an objection to the truth table for material implication: I've never been satisfied with the argument that two false propositions create a true implication however. What good justifications are there for agreeing with this? You seem to misunderstand proof ...


9

The the set {¬,∨,∧,⇒,⇔} is usually used because it includes the "most natural" ones. If we start with a minimal set, like {¬,⇒}, the other ones are usually introduced as abbreviations. There is no "deep" reason : mainly tradition, and a "reasonable" trade-off between savings (minimality) and readibility (to express p ∧ q as ¬(p ⇒ ¬q) is not so "natural".


8

From Jan von Plato, Elements of Logical Reasoning (Cambridge UP, 2013), pag 10 : The two sentences "if A, then B" and "B if A" seem to express the same thing. Natural language seems to have a host of ways of expressing a conditional sentence that is written A → B in the logical notation. Consider the following list : From A, B follows; A is a ...


7

Option b looks correct to me. Your descriptions for a and b seem to be the wrong way round. Option c says that anything that is both a dog and a cat and well-trained is a good pet. Option d is weird - it says that if anything is a cat then well-trained dogs are good pets.


7

You can't, because it isn't valid. Think about it with numbers, consider: a=1 b=2 c=1 It's true that a≠b & b≠c, yet a=c.


6

One should keep in mind that the meaning of "logic" changed over the last century, and is now more confined to formal logic, although it is broader than deductive or mathematical logic in the narrow sense. The interface between the formal and the informal, formalization, formal semantics, is also included. But this is not what Kant meant by "transcendental ...


5

HINT Here is a proof with Natural Deduction : 1) ¬(¬¬¬P ∨ P) --- assumed 2) ¬P ∨ P --- Law of Excluded Middle (is a tautology) 3) P --- assumed [a] 4) ¬¬¬P ∨ P --- from 3) by ∨-introduction 5) ¬P --- assumed [b] 6) ¬¬¬P --- from 5) by Double Negation : φ ⊢ ¬¬φ 7) ¬¬¬P ∨ P --- from 6) by ∨-introduction Now, from 3)-4) and 5)-7) we have derived ¬¬¬...


5

You can try to prove it by cases (∨–Elim). The general form is: If you have: ⊢ (A ∨ B), A ⊢ C, and B ⊢ C Then you can conclude: (A ∨ B) ⊢ C This means that if you've proved (A ∨ B) and you have proved (i) C from assumption A, and (ii) C from assumption B, then you have proved C from assumption (A ∨ B). ...


5

(A) : For the left-to-tight direction we have : 1. P v Q _ | 2. ¬Q --- assumed [1] | 3. P --- assumed [2] for v-Elim | 4. P --- from 3 | 5. Q --- assumed [3] for v-Elim | 6. ⊥ --- from 2 and 5 by →-Elim (recall that : ¬Q is abbrev for Q → ⊥) | 7. P --- from 6 by ⊥-Elim | 8. P --- from 3-4 an 5-7 with 1 by v-Elim, discharging [2] and [...


5

gnasher729 raised an important point that deserves some expansion: "In formal logic, implication x ⇒ y and equivalence x ⇔ y are very obviously useful - they directly express the possibly most important concepts of formal logic." The main point that I want to bring up is this: Naive set theory is not the only important set theory, and Classical logic is not ...


5

There are really so many way to do this and which one you choose largely depends on your personal preference. Here are some: Predicate (∃x)(Lx), where Lx stands for 'x is a leprechaun' (this is your suggestion). ¬(∀x)(¬Lx), less expressive than the first, just to show that there are so many ways to express this. Set (∃x)(...


5

The two different symbols on the page you link to are indeed different. The first is the turnstile symbol Ⱶ which may be read as 'proves', while the arrow → is material implication. These are very different. Material implication is a symbol in the object language defined by the truth table that you give, i.e. T/F/T/T. Turnstile is a symbol in the ...


5

The EI rule formalizes the fact that if we know that ∃xP(x), we are licensed to give to "that P" a name. But we have to avoid that the said name is not already "in use" because, if so, it may denote an object that has some properties incompatible with its "being P". This intuitive restriction is formalized with the proviso : the term (variable or constant) ...


5

Premise : 0) (T⇒E) ∧ (A⇒L). Use Material Implication on the premise to get : 1) (~T∨E) ∧ (~A∨L) Use Simplification to get respectively : 2) (~T∨E) and : 3) (~A∨L) Using Addition on 2) get : 4) (~T∨E) ∨ L Using Association : 5) ~T ∨ (E∨L) Using Addition on 3) get : 6) (~A∨L) ∨ E Using Association : 7) ~A ∨ (L∨E) and using Commutation : 8)...


5

another approach giving the minimum number of steps (though not a formal proof): 1. (P & Q) v ~(P & Q) law of excluded middle 2. (P & Q) v (~P v ~Q) DeM 1


5

It is contentious even to suppose that logic is concerned with being 'self-evident' at all. The old-fashioned idea that logic represents the immutable laws of thought that hold everywhere for all rational beings has fallen by the wayside. Logic has to do with accounting for how it is that some propositions follow from others, or how some combinations of ...


4

We need first-order logic with equality. We have : 1) ∀x (Fx ∨ x=c) 2) ¬Fb ∧ Gb 3) ¬Fa → Ga and we want to derive 3) from 1) and 2). I think that the "trick" is to rewrite 1) as : a) ∀x (¬Fx → x=c) b) ¬Fb --- from 2) by ∧-elim c) ¬Fb → b=c --- from a) by ∀-elim d) b=c --- from b) and c) by →-elim (modus ponens) e) ¬Fa --- assumed f) ¬...


4

If you take A -> B to be a material conditional, such that A -> B iff ~A v B is a prior definition rule MC, then a very simple proof might go something like this: A->A (established in the subproof below:) A (suppose for a conditional) A (by reiteration) A->A (by conditional proof ~A v A (by MC) But the actual details of ...


4

A summary of the rules can be found here. 1. P(x) v Q(x) hyp 2. ~P(x) hyp 3. | P(x) hyp |------ 4. | ⊥ ⊥ Intro 2, 3 5. | Q(x) ⊥ Elim, 4 6. | Q(x) hyp |------ 7. | Q(x) Reit 6 8. Q(x) v Elim, 1, 3-5, 6-7


4

You can use a parse tree for this. First you draw the parse tree, then you draw boxes around subtrees.             And you see that you were correct. Note for example that ∀y ∀x (x ∈ y ∨ y ∈ x) is equivalent to a subformula (namely the whole formula), but not a subformula itself,...


4

The "basic" mathematical logic axioms for identity are : x = x (reflexivity) x = y → y = x (symmetry) x= y ∧ y = z → x = z (transitivity). Thus, from a = b we can derive b = a by simmetry, and from a=b and a=c, we derive c=a from the second one by symmetry and then, from c=a and a=b, we derive c=b by transitivity, followed by b=c by symmetry ...


4

I know that Mauro's answer is what you were looking for. However, in group theory, the term 'identity' has another meaning, which may be the one people coming here from search engines will be looking for. For example, in an additive group (that is, a set of numbers with the + operation; e.g. (N, +)), the identity is 0, because x + 0 = x, for every x. In ...


4

I agree with your first symbolization : (∃x)(Lx), because it seems more "natural" to assume that "leprechaun" denotes a species and not an individual; in fact, you are saying : "leprechauns exist". But in this way we cannot prove anything; the standard semantics for first-order logic assumes that any interpretation has a not empty domain M. This means ...


4

The verum (⊤) and the falsum (⊥) are 0-ary connectives. Thus, we can "read" them also as formulae. If we are working in first-order logic, ⊤ and ⊥ are atomic formulae, because they are "indecomposable" into sub-fomulae. See e.g.: Ian Chiswell & Wilfrid Hodges, Mathematical Logic (2007), page 33 and pages 117-19. But see J Marcos'answer: they are not ...


4

Either one is correct. For some technical purposes it is convenient to bring all the quantifiers out to initial position as in your second version. For that, see "prenex normal form" on Wikipedia. But other purposes might favor the first version and first order logic per se just finds them equivalent.


4

You are right : the correct way is to use proof by cases: 1) Q --- assumed for the proof by cases [a-1] 2) P → Q --- from 1) by →-intro 3) ¬P --- assumed for the proof by cases [a-2] 4) P --- assumed [b] 5) contradicition ! 6) Q --- from 5) 7) P → Q --- from 6) by →-intro, discharging [b] and it is done.


4

From the Polish logician and philosopher Jan Łukasiewicz who invented the Polish notation for logic (named after his nationality) : M ϕ for możliwość : possibility L ϕ for konieczność : necessity [unfortunately: K was alredy used for koniunkcja : conjunction]. For M, see Jan Lukasiewicz, Selected works, North-Holland (1970), Philosophical remarks on ...


Only top voted, non community-wiki answers of a minimum length are eligible