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
1answer
96 views

$P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations.

Suppose that the domain of the propositional function $P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations. a) ...
1
vote
2answers
130 views

Truth table of proof by contradiction

The following is the truth table for an implication: $(T\Rightarrow T) = T$ $(T\Rightarrow F) = F$ $(F\Rightarrow T) = T$ $(F\Rightarrow F) = T$ Now, in an implication involved in a proof by ...
0
votes
2answers
38 views

The propositional logic expression for ∃x∀yP(x,y)

Where u.d. of x is {1,2,3} and y is {a,b} The given answer is ((1,a)Λ(1,b)) V ((2,a)Λ(2,b)) V ((3,a)Λ(3,b)) But I get the expression ((1,a)V(2,a)V(3,a)) Λ ((1,b)V(2,b)V(3,b)) Why is my one wrong ...
2
votes
3answers
43 views

Proving logical equivalences

The question is to prove $\neg (p \wedge q) \to (p \vee r)$ equivalent to $p \vee r$ So far, I got $¬[¬(p \wedge q)] \vee (p \vee r)$ - implication $(p \wedge q) \vee (p \vee r)$ - ...
0
votes
1answer
26 views

Simpliest Propositional Equivalences proof question

I'm solving some propositional equivalences questions and I just want to make sure that following two logics. If, $p \land q = q \land p$ $p \vee q = q \vee p$ in any case, are correct because ...
1
vote
1answer
53 views

Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators.

Earlier this day I ask about the assignmet: Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators. I was given the hint that I could use De Morgan law to show ...
0
votes
5answers
114 views

Logical equivalent of $p\to(q\to p)$

Is Logical equivalent of $p\to(q\to p)$, $p\to(p\wedge q)$ or $p\to(p\vee q)$? I have a truth table: $$\begin{array}{c|c|c|c} p&q&p\wedge q&p\vee q&q\to p&p\to(q\to ...
0
votes
1answer
32 views

Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators [duplicate]

Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators Can someone give a hint?
1
vote
1answer
54 views

How can I show logically equivalence without a truth table

Show that $(p \rightarrow q) \wedge (p \rightarrow r)$ and $p \rightarrow (q \wedge r)$ are logically equivalent. I tried to do this making a truth table but I think my teacher wants me to solve it ...
0
votes
1answer
31 views

Logic question in propositional calculus

How do we prove the following formula for all natural numbers $n$ in propositional calculus $[(q_{1}\vee q_{2}...q_{n})\wedge((q_{1}\Longrightarrow r)\wedge(q_{2}\Longrightarrow ...
1
vote
1answer
83 views

Proving $\vdash (p\to q)\lor (q\to r)$ using natural deduction

I'm trying to prove the following: $\vdash (p\to q)\lor(q\to r)$ using only intuitionistically valid rules. I've tried a few different ways, and I think my problem is that I'm not sure what ...
1
vote
2answers
58 views

Value V on some formula in Logic

I want to calculate, how many value $v$ on {$p,q,r$} has, such that sentence $(p \to (q\wedge r)) \to r$ gets value $0$? I solve it via truth table, any other methods for solving such questions? or ...
1
vote
2answers
29 views

How to express sample space

I have been given No answers though please!
0
votes
2answers
81 views

Question about propositional logic

I was just learning the truth table of the propositional logic . I understand the truth table for the conjunction and disjunction because they make sense in the real life. The conjunction A∧B means "A ...
0
votes
0answers
8 views

how many symantec equations is there in propositional calculus with n boolean variables?

how many symantec equations is there in propositional calculus with n boolean variables? The answers are: 1) 3^n 2) n 3) 2^(2n) 4) 2^n I think the answer is 2^n. Do you think its correct? ...
0
votes
1answer
63 views

Admissible rule in classic logic [closed]

The classical propositional logic admits the concept of admissible rule, and would like some examples of propositional calculus with the 'admissible rule', on wikipedia I don't quite understand...
1
vote
0answers
37 views

Monotonic operators in classical logic

Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
1
vote
0answers
33 views

Can the OR function be linearly separated?

I have two questions regarding linear functions and propositional calculus: 1) How do you decide if, for example, the OR function can be linearly separated? The answer is Yes, however I don't know ...
2
votes
1answer
95 views

Predicated needed for proof using structural induction

I have a set, $F$, of boolean formulas defined inductively as follows: $X_{i} \in F, \: \forall i \in \mathbb{N} \: \text{(variables)}\\ A \in F \implies \neg A \in F\\ A, B \in F \implies A \land B ...
1
vote
2answers
54 views

Proof by cases and contradiction. Is this valid?

Say i have a hypothesis of the following form: $P \lor Q$ and a conclusion $\neg A$. I try a proof by contradiction; so I assume $A$. Now what I am trying to do is break the hypothesis into cases, so: ...
1
vote
1answer
45 views

Deduction theorem with undischarged statement

I am reading "Mathematical logic" by Ian chriswell and Hodges and at one point in the text they mention the deductive theorem (page 17) which states; If $\Gamma \cup \left \{ \phi \right \} \vdash ...
0
votes
2answers
89 views

How can I indicate a truth table if its Valid or Invalid?

Construct a truth table for Destructive Dilemma using the general symbolic notation for the rule of inference, T for true value, F for false value. Indicate whether valid or invalid. Is this the ...
5
votes
2answers
78 views

Are there some techniques for checking whether a statement implies another without truth tables?

Are there some techniques for checking whether a statement implies another without truth tables? For example, I was asked whether $P\Longrightarrow P_{1}$ given the following statements: $$P: [p ...
0
votes
1answer
69 views

How to prove a tautology using proof by contradiction?

I am trying to learn proof by contradiction. How would i go about proving that ((A => B) and (C => D)) => ((A => D) or (C => B)) is a tautology, ...
6
votes
2answers
99 views

The logical law of closed systems of sentences

Consider the usual logical connectors $\wedge, \vee, \supset, \neg$ (i.e., "and", "or", material implication, negation) and the "stroke" $/$ defined as $p / q := (\neg p) \vee (\neg q)$. In his book ...
0
votes
1answer
24 views

Prove conjecture using premises

I have three premises with me defined: $(B \land L) \implies A$ $(A \land D) \implies \lnot H$ $\lnot J \implies (D \land \lnot H)$ I need to prove the following conjecture with the help ...
1
vote
6answers
125 views

Why is $P \to Q \equiv \neg P \vee Q$?

By truth table, we know that $P \to Q$ is equivalent to $\neg P \vee Q$. But I'm trying to understand why this work? How can connective "or" be implication. I tried some examples but I still can't ...
2
votes
2answers
45 views

Is the following propositional function well defined?

My question is fairly simple: Is $(P \wedge Q)(x)$ equivalent to $P(x)\wedge Q(x)$? Reason I'm asking, is that when I asked my tutor he said the statements weren't equivalent because if $P(x) = "x\ ...
0
votes
1answer
146 views

Proving a property about logical entailment

I have an intuitive idea that, given some set of formulas $Γ$, and two formulas $A, B \not\in Γ$, $((Γ\cup{A}) \models B)↔(Γ \models (A→B))$. I can rationalize this as, if the left side of the ...
0
votes
1answer
56 views

Is an argument valid simply if its form is valid?

Can I conclude that an argument is valid if its argument form is valid? I realize that a false premise may lead to an incorrect conclusion (which is not what I'm asking). I see a lot of questions ...
1
vote
1answer
91 views

Logical implication and valid arguments question

The following is a valid argument: $[[p \lor (q\lor r)]\land \neg q] \rightarrow (p\lor r)$. Determine the rows of the table crucial for assessing the validity of the argument and which rows can be ...
0
votes
0answers
42 views

Glivenko's theorem for propositional logic: $\neg\neg A, \neg\neg(A \rightarrow B) \vdash \neg\neg B$. [duplicate]

In proving Glivenko's theorem for propositional logic I have found myself not able to prove the following: $\neg\neg A, \neg\neg(A \rightarrow B) \vdash \neg\neg B$. The only inference rule I have is ...
0
votes
1answer
117 views

Proving De Morgan's Law with Natural Deduction

Here is my attempt, but I'm really not sure if I've done it right; as I'm just about getting the hang of Natural Deduction technique. Have I done it correctly? If not, where did I make errors and ...
1
vote
0answers
60 views

Dual formula in propositional logic

There's something I don't understand in my course on propositional logic. In the case of x being a variable, the definition of its dual is x* = x. Right. However, further in the course, there's a ...
1
vote
1answer
119 views

Finding a formula for the number of equivalence classes using $m$ variables and $\rightarrow$

I need to find a formula for the number $n_m$ of equivalence classes of the set of propositional logical formulas only containing the propositional variables $p_0,...,p_m$ and only using the ...
1
vote
1answer
46 views

Proof of equality using basic axioms

I'm supposed to prove equivalence associativity using propositional logic axioms. My teacher insists that I use mathematical symbols. Half of the proof is given and I am to derive the second half. ...
3
votes
3answers
140 views

Proving using axioms of propositional logic

As part of my upcoming exam in Mathematical Logic we are supposed to be able to prove a given statement using a list of given $axioms$, $M.P.$ and $H.S.$ My question is, how do I approach these kinds ...
2
votes
1answer
67 views

How do I prove the tautology $\vdash((p\rightarrow q)\rightarrow p)\rightarrow p$ using natural deduction?

I'm trying to prove $\vdash((p\rightarrow q)\rightarrow p)\rightarrow p$. The best attempt I can come up with is as follows: $((p\to q)\to p)$ Assumption $p\to q$ Assumption $p$ ...
7
votes
4answers
188 views

Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ {without truth table}

Problem: Show $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ Source: As was noted in the original post, this problem is from Daniel J. Velleman's book ...
4
votes
1answer
63 views

Simplify $(p\land q)\lor(p\land \neg q)$

So I was asked to simplify this statement $S$: $$(p \land q) \lor (p \land \neg q)$$ My understanding is that it needs to have a similar truth table, though I'm not sure if that's exactly right. ...
3
votes
1answer
78 views

Do we actually define implications using an implication itself?

Everything in math stems from definitions. Eg: Let an 'implication' be defined as ... But any such 'let' actually means 'if it be true that'. So what we're really saying is 'If an implication be ...
2
votes
0answers
77 views

Show equivalence of statement $\left(P\rightarrow Q\right) \wedge \left(Q\rightarrow R\right)$ to … [duplicate]

Show that $\left(P\rightarrow Q\right) \wedge \left(Q\rightarrow R\right)$ is equivalent to $\left(P\rightarrow R\right) \wedge \left[\left(P\leftrightarrow Q\right) \vee \left(R\leftrightarrow ...
2
votes
3answers
170 views

Problem solving Logical Equivalence Question

I am working with Logical Equivalence problems as practice and im getting stuck on this question. Can somebody help? Im trying to show that The LHS is equivalent to the RHS (¬P ∧ ¬R) ∨ (P ∧ ¬Q ∧ ¬R) ...
0
votes
0answers
36 views

Performing arithmetical operations (with binary numbers) using propositional logic

Clarifying some terms. By arithmetical operations I mean the four basic operations of addition, subtraction, multiplication and division. By binary numbers I mean numbers in the binary system. By ...
1
vote
1answer
46 views

Prove $R$ follows from premises $(\lnot R\rightarrow\lnot Q),\;(P\lor Q,),\; (\lnot(P \lor T))$

I'm preparing for an exam and we weren't given an answer sheet. I'd like to know if my reasoning for the given conclusion is correct? Premises: $(\lnot R) \rightarrow (\lnot Q),\;\; (P \lor Q),\;\; ...
2
votes
1answer
33 views

Consider the statement and decide which of the following implies that this statement is true.

Consider the statement: If Bill takes Sam to the concert, then Sam will take Bill to dinner. Which of the following implies that this statement is true. $\\$ a. Sam takes Bill to dinner only if ...
0
votes
1answer
48 views

Using rules of inference with quantified statements

Use rules of inference to show that (a) $ ∀x (R(x) → (S(x) ∨ Q(x))$ $∃x (¬S(x))$ $ ∃x (R(x) → Q(x) )$ I'm kinda lost at what to do... I can start but don't know what to do afterwards 1) $R(a) ...
0
votes
1answer
53 views

Immediate consequence in Gödels incompleteness paper

In the famous paper, “On Formally Undecidable Propositions of PM”, $c$ is defined as the immediate consequence of $a$ and $b$ if $a$ is the formula $\lnot b \lor c$. How does this relate to the ...
4
votes
1answer
80 views

Formal proof of $P\to Q, (P\to Q)\to (T\to S), \neg Q, P\lor T\vdash S$

This is an example exam question that I'm wondering if I did right? We weren't given an answer key, so I'm checking to make sure I'm comprehending the material and if my answer is correct? Premises: ...
0
votes
2answers
73 views

help verifying my answer for this“ premise-conclusion” question

For each of the premise-conclusion pairs below, give a valid step-by-step argument (proof) along with the name of the inference rule used in each step. (a) Premise: {¬p ∨ q → r, s ∨ ¬q, ¬t, p → t, ...