Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

1
vote
3answers
114 views

When proving the Hypothetical Syllogism inference rule, why must you assume that p is true?

I recently started learning Discrete Maths and currently studying rules of inference. I was looking at a proof of Hypothetical Syllogism, aka: P→QQ→R∴ P→R and I came across this proof of the ...
0
votes
2answers
57 views

Prove/disprove if $a\vee b \Rightarrow c$ then $a\Rightarrow c$ or $b\Rightarrow c$ and vice versa

$a,b,c$ are statements, $\Rightarrow$ is a tautological consequence (not a logical implication and it's not a proposition). Prove/disprove: if $a\vee b \Rightarrow c$ then ...
0
votes
1answer
85 views

Disjunctive normal form (BOTH dnf and cnf) example help

T or ( not x and y ) or ( x and y ) In class we went over examples of how many things can be both DNF and CNF... eg. (not z) or y can be thought of as both (not z) or y .... dnf ((not z) or ...
1
vote
2answers
100 views

Prove/disprove if $a,b\Rightarrow c$ then $(a\Rightarrow c) \vee (b\Rightarrow c)$ and vice versa

Let $a,b,c$ be statements, $\Rightarrow$ is a tautological consequence. Prove/disprove: if $a, b\Rightarrow c$ then is it necessarily $a\Rightarrow c$ or $b\Rightarrow c$ ? if ...
0
votes
1answer
59 views

equivalence laws example proof

Problem taken from here. Use Logical Equivalences to prove that $[(p \land \lnot(\lnot p \lor q)) \lor (p \land q)] \implies p$ is a tautology. implication law... $\lnot[(p \land \lnot(\lnot p ...
0
votes
1answer
48 views

How to prove this distributive law using natural deduction

$(q \lor r)\wedge p\vdash(q\wedge p)\lor (r\wedge p)$ After making the first assumption and splitting it up using ∧-elimination, I get stuck. Can anyone help?
0
votes
2answers
51 views

Propositional Logic - Exactly what does ~ (negation) mean

Let's say p is a statement. Is ~p (negation of p) just opposite of p or is it anything but p. For example, let's say p = "None of the basketball players are blond" Without just adding a 'not' in ...
5
votes
5answers
119 views

How can it be that $(P \rightarrow Q) \vee (Q \rightarrow P)$ is a tautology?

I consider $(P \rightarrow Q) \vee (Q \rightarrow P)$, that is $(\neg P \vee Q) \vee (\neg Q \vee P)$ and so $\neg P \vee Q \vee \neg Q \vee P$, which is a tautology. It seems strange to me that, ...
2
votes
1answer
46 views

Logic Invalidity

I'm having trouble with a problem in Propositional Logic Using induction I am supposed to show that if a well formed formula (wff) X has no repetitions of sentence letters then X is invalid. The hint ...
3
votes
1answer
83 views

Online tools for checking validity of classical, intuitionistic, … logic formulas?

What online tools are available, where one can enter a formula of (first order) propositional or predicate logic, and have it check whether it is valid classically, intuitionistically, or even ...
1
vote
3answers
63 views

Proving that $\{p\to q, p\to \neg q\}\Rightarrow\neg p$

Prove the following: $\{p\to q, p\to \neg q\}\Rightarrow\neg p$, that is, prove that $\neg p$ is a tautological consequence of $\{p\to q, p\to \neg q\}$ (Note: I write $0,1$ instead of $F,T$.) ...
1
vote
1answer
57 views

Is it valid to make an assumption that directly contradicts a given premise?

Is it valid to make an assumption that directly contradicts a given premise? For example, if I want to deduct the proposition $$¬(p→q) ⊢ p∧¬q$$ I'd like to assume $p→q$, so I can falsify things ...
4
votes
3answers
968 views

How to express the statement “not all rainy days are cold” using predicate logic?

I am trying to figure out how to express the sentence “not all rainy days are cold” using predicate logic. This is actually a multiple-choice exercise where the choices are as follows: (A) $\forall ...
0
votes
2answers
73 views

Proving equivalency using boolean algebra laws of logic

I have a question on my exam papers relating to proving equivalences using the laws of logic, but I'm not sure how to work it out as I don't have the solution paper. Can someone explain to me the ...
0
votes
2answers
38 views

Principle of propositional congruence

Let $\varphi$ be a propositional formula, defined as a formula containing propositional symbols and connectives only, and let $\psi,\chi$ be propositions. I read the following principle of ...
2
votes
3answers
83 views

Propositional Logic Tautology Proof

I have question about a proposition that I need to prove is a tautology: $((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ I have tried negating the first large bracket, ...
5
votes
2answers
53 views

Propositional Logic Help

I need to prove that $(\neg p \wedge (p \vee q)) \rightarrow q $ is a tautology using Laws of Logic (not truth tables). This is what I tried: $\equiv (( \neg p \wedge p) \vee (\neg p \wedge q)) ...
0
votes
2answers
35 views

Logical equivalence: Which side is better to start to obtain the other?

How to resolve this with steps please: $$p \to (q \lor r) \equiv (p \to q) \lor (p \to r)$$ I just don't get how with less variable we can have more after or with more we can have less?
1
vote
2answers
43 views

Find logic expression for given truth table

So I was given this truth table and I need to find a logical expression for the formula to give such a result (where there can be two or three 2-place connective expressions (e.g. $A \lor B$ counts as ...
0
votes
2answers
55 views

Weird logic question I need help with!

The professor tells Jim: "It is necessary that you get at least a B on the final in order to pass the course". Jim gets a B. What can she conclude? a) He passed b) He can conclude nothing... I ...
2
votes
1answer
62 views

Prove $ \vdash \alpha \to \alpha $ in minimal logic of Hilbert

$ \vdash \alpha \to \alpha $ I'm trying to find a way solving this statement using minimal logic of Hilbert which have only two axiom's K & S and one only rule the modus pones (MP) : ...
2
votes
1answer
30 views

Proving a variable true through rules of inference

Question: Use rules of inference to show that if $(p → q) ∧ (q → p),\; t ∨ q,\; t ∨ p,\; (p ∧ q) → t$, then $t$ is true. Work So Far: $$\text{1. }(p \implies q) \land (q \implies p)\text{ | ...
1
vote
3answers
72 views

Propositional Logic : Why is ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)

I was working my way through some Propositional Logic and had the following doubt : Why is this true : ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ ...
0
votes
1answer
29 views

$p\to\neg q, q \vdash \neg p$- natural deduction

I have the following proposition: $$p\to\neg q, q\vdash \neg p$$ Using the following formulas on propositions is easy enough: $$\frac{\psi \qquad \psi\to\varphi}{\varphi}\quad \to_e$$ ...
0
votes
1answer
94 views

prove $( \lnot \lnot p \Rightarrow p) \Rightarrow (((p \Rightarrow q ) \Rightarrow p ) \Rightarrow p )$ with intuitionistic natural deduction

I'm trying to prove this statement with intuitionistic natural deduction using inference rules like this example : this is the statement I'm trying to solve : $$( \lnot \lnot p \Rightarrow p) ...
2
votes
1answer
40 views

$p \to (q\vee\neg r), \neg q, r ⊢ \neg p$ - Natural deduction- elimination with $\neg$ operator

I have the following proposition: $$p \to (q\vee\neg r), \neg q, r ⊢ \neg p$$ The only part I have trouble with is the : $$p \to (q\vee\neg r)$$ Clearly the first step is to eliminate $q$ or $\neg ...
2
votes
3answers
63 views

What is the correct form of De Morgan's Law in logic?

According to wikipedia (link), Morgan's Law is: $$¬ (P \wedge Q) \Rightarrow (¬P) \vee (¬Q)$$ But if you scroll down to 8.2.2 on this page (link), it says that Morgan's Law works as follow: $$¬ (P ...
0
votes
1answer
77 views

Prove tautology without truth using a truth table. [duplicate]

I am struggling to prove, without using truth tables, that the statement is a tautology. [(p→q)∧(q→r)]→(p→r) My work so far... ¬[(¬p∨q)∧(¬q∨r)]∨(¬p∨r) ...
-1
votes
1answer
44 views

Proof that the formula $((p\to q)\land (q\to r)\land p)\to r$ is a tautology [duplicate]

Write down the assumptions in a form of clauses and give a resolution proof that the formula is a tautology. $((p\to q)\land (q\to r)\land p)\to r$ I got information that i need to use here ...
1
vote
1answer
54 views

Truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ : What should my next step be?

I am working on a truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ This is what I have done so far: My next step would be to do the disjunction from the first two ...
5
votes
4answers
118 views

Show that $(p \to q) \lor (q \to p)$ is a tautology

i tried to prove that $(p \to q) \lor (q \to p)$ is tautology i used p and not-q as conditions. (Premises 1 and 5) I managed to get to a solution but I'm not sure if it's right. can you please check ...
0
votes
2answers
61 views

How can i get a tautology truth table from using 3 variables?

I am looking to use the variables p, q and r to create a truth table which concludes to a tautology.
0
votes
1answer
44 views

Proving an “OR” statement

If one wants to proof $P\vee Q$, is it sufficient to proof $\lnot P \rightarrow Q$? Because it makes intuitively more sense to me that $P\vee Q$ would be logically equivalent with $(\lnot P ...
0
votes
3answers
37 views

Propositional logic problem: Sales, expenses and happiness of the boss

Either sales will go up and the boss will be happy, or expenses will go up and the boss won’t be happy. Therefore, sales and expenses will not both go up. I know the solution is that the ...
3
votes
2answers
107 views

Principle of explosion: Other arguments?

I've come across a proof-theoretic argument for explosion on Wikipedia, which is as follows: $A \ \ \wedge\sim A$ $A$ $ \sim A$ $ A \lor B$ $B$ $(A \ \ \wedge \sim A) \implies B$ I've thought of ...
3
votes
2answers
53 views

Difference between “necessary” and “necessary but not sufficient”?

This is from Discrete Mathematics and Its Applications: Let $p, q,$ and $r$ be the propositions: $\quad p:$ Grizzly bears have been seen in the area. $\quad q:$ Hiking is safe on the ...
0
votes
1answer
128 views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
1
vote
3answers
339 views

Is there a quicker way to check if this proposition is self contradictory?

I have been trying to refresh my memory with regards to classical logic. As a result, I am currently going over the basics. The following proposition seems to be false in all possible worlds. ...
-2
votes
2answers
79 views

Can anyone help me with a solution? [closed]

Write down the assumptions in a form of clauses and give a resolution proof that the proposition $$\Big((p \rightarrow q) \land ( q \rightarrow r) \land p \Big) ...
0
votes
1answer
70 views

Can someone verify my assertion from this english sentence? [duplicate]

This is from Discrete Mathematics and its Applications This is the book means when mentions a list of common ways to express conditional statements After going through the list, I immediately ...
0
votes
1answer
34 views

Need to prove that a conditional statement is a tautology

The conditional statement is $[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$ Here are the steps I took in an attempt to prove the above statement a tautology, but I ...
2
votes
1answer
94 views

Show that the conditional statement is a tautology without using a truth table

I have been attempting to use identities to get to the answer but I am unable to get anywhere. Here is the equation I am trying to prove tautological without using truth tables: $[(p\rightarrow q) ...
2
votes
1answer
35 views

odd logical structures

How you find contrapositive and converse of these sentences. Only if John chops down the tree, will he be a lumberjack. You can't win if you don't fight. All people that root for the Ducks are from ...
1
vote
2answers
48 views

Propositional Logic : Absorption - Why is it so?

Why is the Absorption Law of Propositional Logic so ? p $\lor (p \land q) \equiv$ p Would appreciate an intuitive explanation and not one using a Truth Table
3
votes
2answers
41 views

Is my deduction of $t$ being true logically correct?

According to the problem on my homework (yes, this is my homework), number 42 in chapter 2.3 of Discrete Mathematics with Applications by Susanna S. Epp, the following are true: \begin{align} ...
1
vote
1answer
53 views

Use logical equivalencies to classify as tautology, contradiction, or contingency.

Classify the following as tautologies, contradictions or contingencies using logical equivalences. Can anyone let me know what I'm missing or doing wrong? I got stuck, here is what I have so far: ...
1
vote
5answers
339 views

Which can be logically inferred from the given statements?

All women are entrepreneurs. Some women are doctors. Which of the following conclusions can be logically inferred from the above statements? (A) All women are doctors. (B) All doctors are ...
0
votes
0answers
34 views

Expansion Of A algebric term

While doing a coding for software I fell upon in the need to expand the following expression $(A \land B) \land (C \land (D \lor (E \land f)) \land (g \lor h \lor i))$ I tried it and result I got is ...
1
vote
5answers
132 views

Necessary but not sufficient in logic

I am working through sample questions and am having a bit of trouble understanding the solution. Write using logical connectives: p : Grizzly bears have been seen in the area. q : Hiking is safe on ...
1
vote
1answer
37 views

Are these two statements logically equivalent?

Are the statements $D \Rightarrow H \vee S$ and $(D \Rightarrow H) \vee (D \Rightarrow S)$ logically equivalent?