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)

2
votes
1answer
45 views

Express $(A\to B)\land((C\land B)\to A)$ using biconditional

Is there a way to express the formula $(A\to B)\land((C\land B)\to A)$ as a biconditional, i.e. as a statement of the form $\phi\leftrightarrow\psi$ for some expressions $\phi(A,C)$, $\psi(B,C)$? Of ...
0
votes
2answers
200 views

Prove using a proof sequence and justify each step

Prove using a proof sequence that the argument is valid [ A --> (B ∨ C) ] ∧ B' ∧ C' --> A' I'm having some trouble figuring the proof out here. Here is what I have so far. Is this on the right ...
2
votes
0answers
39 views

How can i solved this using fitch notation?

I have a little problem that is proof this following statement using fitch notation, can anyone help me out? :) |= (t → s) ∧ ¬((s → q) → (t → q)) Thanks in advance.
1
vote
2answers
48 views

Are the following contradictions?

I have the following: $p\to (q\land p)$ $p\to \neg (q\land p)$ I am asked if they are contradictions, can someone explain what that means exactly. I did a truth table for both, and if ...
1
vote
1answer
37 views

Logic - Simplifying a propositional logic expression

So my teacher was showing us an example in class and then blasted through it during the last minutes of the class. He does not respond to his emails outside of his office hours, so I was wondering if ...
0
votes
1answer
38 views

Conjunctive Normal Form Conversion

The question is to turn the following formula into Conjunctive Normal Form: $\rm \neg [(p \vee q) \wedge (r \to s)] \to p \wedge \neg q \wedge \neg s$ I have come up to here: $\rm \neg [(p ...
3
votes
1answer
52 views

Tautology - First Order Logic

I have a question in my exam practice, to determine if the following statement is a tautology, in First Order Logic: I think it is a tautology, but am I correct? In my course the proffesor told us ...
0
votes
1answer
22 views

How do I notate a proposition with multiple conditions?

Lets's say I have the predicates: F(x) means x is even G(x) means x is a prime number and we take the universe of discourse to be the set of natural numbers N = {1,2,3,...} How do I notate a ...
1
vote
0answers
28 views

Translation into the propositional logic

How could the following sentence be translated into the propositional logic? Since I am here I talk to you. Do I have to use implication like p -> q?
0
votes
3answers
44 views

$p\land\neg q\to r, \neg r, p ⊢ q$ -natural deduction

I have the following: $$p\land\neg q\to r, \neg r, p ⊢ q$$ I know that my attempt is incorrect, but I will show it anyways: Step 1) $p\land\neg q\to r$ ----premise Step 2) $\neg r$ -----premise ...
2
votes
1answer
50 views

$⊢p \land q \to (p\to q)$ - Natural deduction proof confusion

I have the following: $$⊢p \land q \to (p\to q)$$ I'm having a difficult time trying to figure out where to begin. I believe that I am supposed to assume p and ...
2
votes
2answers
88 views

If $s_{1}\Longleftrightarrow s_{2}$ then $s_{1}\leftrightarrow s_{2}$ is a tautology?

I see that it's not always the case for $s_{1}\leftrightarrow s_{2}$ is a tautology. As if I have $s_{1}:p$ and $s_{2}:q$, I have the following truth table: $$ \begin{array}{c|c|c|c|c|c|c} p & q ...
1
vote
1answer
26 views

Can there be a vacuous tautological consequence $F\vDash F$?

Can there be a vacuous tautological consequence $F\vDash F$? Since $α⊨φ \iff ⊨α→φ$ then is: $(k∧¬k)⊨(p∧¬p)$ for example considered a tautological consequence?
1
vote
3answers
79 views

Need Help with Propositional Logic

I am stuck with this proof. I am trying to use deduction (or induction I think) to prove for a tautology with logic laws like De Morgan's, distributive , and implication law etc. Note: I am not ...
-1
votes
1answer
56 views

Finding a formula in intuitionist logic [closed]

I am looking for a formula which is true semantically but not syntactically in propositional intuitionist logic. Does it exist? If yes what's that? Thanks for your help.
1
vote
1answer
17 views

Proving $a\equiv b \iff F_a=F_b$, $F_a=\{c\mid a\vDash c\}$

Let $a$ be a proposition (atomic or not), and let $F_a=\{c\mid a\vDash c\}$ is the set of all the propositions that are tautological consequence of $a$. Prove that $a\equiv b \iff F_a=F_b$. ...
1
vote
1answer
72 views

Modus tollens - Negations on the implication

This is likely a basic question however based on my textbook definition of Modus tollens it looks like this: $$\neg q$$ $$\frac{(p \implies q)}{\neg p}$$ I however have something that looks like ...
5
votes
2answers
193 views

Why isn't Modus Ponens valid here

I have the following: $(\neg A \lor B) \rightarrow (\neg A \lor B) \\ (\neg A \lor B) \\ \vdash \neg A \lor B $ And in my mind this seems like a legitimate use of the Modus Ponens rule. But the ...
1
vote
3answers
179 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
63 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
143 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
101 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
91 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
59 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
56 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
123 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
179 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
64 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
60 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
1k 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
79 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
39 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
91 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
55 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
36 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
54 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
57 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
68 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
32 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
74 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
100 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
47 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
68 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
121 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
56 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
58 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
124 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
88 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.