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
41 views

Is ({1, 0}, ⊕, ∨) a field? and Is ({1, 0}, ⊕, ∧) a field?

1 and 0 denote the logical statements True and False. These two questions are for homework so would rather an answer that could help explain it to me then just a straight answer. Thanks to anyone who ...
1
vote
2answers
22 views

Can a propositional function have quantifiers?

According to Wikipedia, an open formula is a WFF without quantifiers. I have read that a propositional function is the same as open formula. Are both of these statements correct? Is it true that ...
1
vote
2answers
68 views

Deducing $((\neg a \to \neg b) \to ((\neg a \to b) \to b)))$ from axioms

I have seen many questions here, using a different set of axioms than mine. Here is mine : $$1) (a \to (b \to a))$$ $$2) ((a \to (b \to c)) \to ((a \to b) \to (a \to c)))$$ $$3) ((\neg b \to \neg a) ...
0
votes
1answer
25 views

What are the roots of propositional logic?

You know, I actually started learning about propositional logic by asking the same question, but about maths. However, now am wondering what the roots are of propositional logic, I mean, we don't ...
1
vote
1answer
22 views

Describe 3-colourable graph in propositional calculus

I am trying to solve the following problem. Let $G=(V,E)$ be a Graph with $V=N$ (natural numbers) and $p_{ij}$ a set of propositional variables for which we have $p_{ij}$ is true <=> $(i,j)\in E$. ...
0
votes
1answer
16 views

Natural Deduction Proof (c ∧ n) → t, h ∧ ¬s, h ∧ ¬(s ∨ c) → p |− (n ∧ ¬t) → p

I'm trying to do a question from Huth and Ryan's book 'Logic in Computer Science' and I am stuck on the following natural deduction proof: prove by natural deduction that the sequent (c ∧ n) → t, h ...
1
vote
1answer
14 views

Understanding predicate logic given symbolic notation?

I'm having trouble understanding predicate logic. Question J is that saying "All broken windows are in the garage"? Is K. saying "for every x in the garage the x has a broken window" L.) "there ...
0
votes
1answer
10 views

Logic Proof using Inference rules and replacement rules

I am trying to prove the following using the inference and replacement rules in logic: (A . F) ⊃ (C ∨ G), ~ (C ∨ (F . G)), F ≡ ~ (X . Y), ~ (X ∨ ~ W) /∴ ~ (A ∨ X) I have this so far: Work But I do ...
0
votes
0answers
23 views

Proving theorems using the Compactness theorem

We say an infinite set $S$ is closed under $\wedge$ if for all $a,b$ $\in S$ so $a\wedge b \in S$. I need to prove that if S is closed under $\wedge$ and for all $a \in S$ we know is that $a$ is ...
2
votes
2answers
30 views

Propositional calculus axiom the other way around

I have the following axioms of propositional calculus (as well as modus ponens and the deduction theorem if needed): $$(a \to (b \to a)) \tag1$$ $$ (((a \to (b \to c)) \to ((a \to b) \to (a \to c))) ...
2
votes
3answers
62 views

Logical limitations of Proofs by Contradiction

In general proofs by contradiction go as follows: Given an arbitrary hypothesis, $\ p \implies q$, we assume $\left(p\implies q\right) = T$, and then we show that by assuming the hypothesis to be ...
1
vote
0answers
31 views

Natural Deduction Proof $\neg(P \to Q) \vdash Q \to P$

I am trying to answer Question 3(e) in Exercise 1.2 of Huth and Ryan's Logic in Computer Science book for revision and I am stuck on it. The question asks you to prove the validity of the following ...
1
vote
0answers
16 views

Logic - logical connective for (~ABC) + (A~BC) + (AB~C)?

Is there a logical connective that says 'True, if and only if 1 proposition is true'. Or perhaps even better, is there one that describes 'True, if and only if n propositions is true'? Where n is an ...
1
vote
2answers
20 views

Commas in propositional logic

I want to know what effect a comma has on a propositional statement. For example: $\{\neg p, p \vee q \} \vDash q$ Does this bit $\{\neg p, p \vee q \}$ mean just $q$? Thanks.
0
votes
1answer
9 views

How to eliminate bi conditionals?

p <--> q can be written as (p → q) ∧ (q → p) (~p V q) Λ (~q V p) After this I am confused. If I distribute Λ over V, I get (~p V q Λ ~q) V (~p V q Λ p) which becomes (~p V q Λ ~q ) V (~p V q ...
2
votes
2answers
920 views

Sudoku Puzzles and Propositional Logic

I am currently reading about how to solve Sudoku puzzles using propositional logic. More specific, they use the compound statement $\bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}~p(i,j,n)$, ...
1
vote
0answers
42 views

When does the dual of $s =s$? [duplicate]

When does $s^*=s$? $s^*$ represents the dual of $s$, where $s$ is a compound proposition involving only $T, F, \wedge, \vee, \neg $, and $s^*$ is obtained by interchanging $T$ for $F$, $F$ for $T$, ...
1
vote
1answer
37 views

Tarski's schema T

On Wikipedia, Tarski schema T says: A sentence of the form "A and B" is true if and only if A is true and B is true A sentence of the form "A or B" is true if and only if A is true or B is true A ...
0
votes
2answers
43 views

Prove $[(P \lor A) \land ( \neg P \lor B)]\rightarrow (A \lor B)$

I want to prove that $[(P \lor A) \land ( \neg P \lor B)] \rightarrow (A \lor B)$, using distributions or reductions (even though I am aware that simpler proofs exist). The issue is that I keep ...
2
votes
1answer
61 views

Generators of the Lindenbaum-Tarski algebra

I am a bit confused about the role of propositional variables in the construction of the free Lindenbaum-Tarski algebra. In the entry "Lindenbaum-Tarski algebra" on Wikipedia, in the section ...
-4
votes
0answers
17 views

prove the proposition using formal logic [on hold]

prove using formal logic $\forall x ( \neg P(x) \lor Q(x)) \vdash \forall x ( \neg H(x) \lor Q(x)) \lor \exists x ( H(x)\wedge \neg P(x))$
0
votes
1answer
41 views

Is there a blackboard bold letter for the set of Boolean numbers? [duplicate]

Is there a symbol (e.g. $\mathbb{B}$) for the special set of Boolean numbers or values; ${0,1}$ or ${True,False}$?
0
votes
2answers
417 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 ...
0
votes
1answer
807 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
1answer
72 views

Complicated FOL Formula {∃a,c(a≠c) ∧ ∀a,c[(a≠c)⇒(h(a,c)⟺ ¬h(c,a))] ∧ ∀a,c[h(a,c) ⇒ ∃b(h(a,b)∧h(b,c)∧b≠c)]} ⇒ ¬{∃a∀b[b≠a⇒ h(a,b)]}

In preparing for an exam, I'm working through old exam questions and am now trying to figure out if the following first-order formula is valid and if not, then give a model that does not satisfy the ...
0
votes
0answers
17 views

Mathematical logic: Predicates, formula

I've got universum $A = \{0,1,2\}$ Predicate: $R^{A}=\{\{x,y\} \in A \times A \hspace{2mm} | \hspace{2mm} x \neq y \} $ Terms: $f^A(x) = 1$ $g^A(x,y) = min(x,y)$ Constant $c^A = 2$ Valuation: ...
2
votes
0answers
56 views

Are these two logical statements equal?

I found this question from a website: "Neither the fox nor the lynx can catch the hare if the hare is alert and quick." Let: P: The fox can catch the hare Q: The lynx can catch ...
0
votes
1answer
31 views

Prove or disprove in propositional calculus

I have the following question - and would like to make clear some definition via it's answer - Prove of Disprove - If $\\X\models\alpha$ and $\\Y\models\alpha$, then $X\cap Y\models\alpha$ ...
2
votes
3answers
103 views

Diffucult Tautology to Prove

I'm trying to show that the following is a tautology: $(p \vee q) \wedge (\neg p \vee r) \Rightarrow (q \vee r)$ Can anyone help, as far as I can get is to the following: $[(\neg p \wedge q) ...
0
votes
4answers
89 views

Why is “$A$ unless $B$” equivalent to $A \lor B$?

$A$ unless $B$ surely means, 'given that $B$ does not happen, $A$ will happen'. So if $B$ happens, $A$ does not happen. Yet I've read, by those officially accredited, that $A$ unless $B$ = $A$ or ...
1
vote
0answers
20 views

From Propositional Calculus Proof to Predicate Calculus Proof

PROVE: If {$\Delta_{i}$} are all deductively closed set of formulae, so is $\cap \Delta_i$. Show with predicate Calculus. Definition: {$\Delta_{i}$} a set $\Delta$ of formulae is deductively closed ...
0
votes
5answers
223 views

Use tableau to convert formula to DNF/CNF form

Is there any method that can be used to convert any formula do a DNF/CNF form using only the truth table? For example if I have the following formula p → ¬(q∨r) How can I convert it into DNF? ...
3
votes
0answers
33 views

Strict order on propositions and interpolation

We can define a strict order on the set of propositions in countably many propositional letters in the following way: $$\varphi\sqsubset\psi \iff (\models \varphi\rightarrow\psi)\, \land (\not\models ...
-1
votes
2answers
72 views

Should we change the truth table for the material conditional?

Having studied logic, I still cannot understand the conditional. At first, it was because (as with most things I learn) it was a problem with my understanding. I now believe it is because there is an ...
3
votes
4answers
48 views

Using Logic Laws to prove $p \leftrightarrow q \equiv (p\lor q)\to(p \land q)$

I am trying to prove that $p \leftrightarrow q \equiv (p\lor q)\to(p \land q)$ and am really lost in the steps to solve this. So far I have: $p \leftrightarrow q \equiv (p\to q)\land(q\to ...
0
votes
2answers
602 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
0
votes
1answer
40 views

Meaning of “$r \to s$ is a tautology” in the definition of “implication” and “equivalence”

What does it mean to say the following: $$ r \to s\ is\ a\ tautology$$ I make the following truth table: $$\begin{array}{ l c c r } r & s & \lnot r & r \to s \\ \hline T & T ...
0
votes
1answer
36 views

Proving general proposition using HPC

If I have a general Proposition $c$ in HPC + another axiom that $(a \rightarrow b)$. HPC axioms - $$1 .a \rightarrow (b \rightarrow a)$$. $$2. (a \rightarrow (b \rightarrow c))\rightarrow ...
1
vote
2answers
40 views

Modus Ponens: why it should not work

The scenario I'm analyzing is the following: I have the set of clauses $${ ( \neg A \Rightarrow B ),\, ( B \Rightarrow A ),\, ( A \Rightarrow ( C \wedge D ) ) }$$ and I have to prove the ...
0
votes
2answers
16 views

Simplifying propositional logic formulae

Prove $\neg ((P\land Q)\lor \neg (P\land T)\lor (Q\land T)) \equiv P \land \lnot Q \land T$ Using only De Morgans Laws and the Distribution Laws. I managed to get the left hand side to reduce to the ...
1
vote
1answer
23 views

Propositional resolution: the correct way to proceed

I'm trying to solve the following exercise: using resolution, tell whether the following formula can be proven: F = {( L $\wedge$ V) $\rightarrow$ H, L $\rightarrow$ V , L } entails (V $\wedge$ H). ...
-1
votes
1answer
10 views

How to use parentheses with one logical conective? [closed]

is (((a and b) and c) and d) equal to a and b and c without parentheses? Why?
1
vote
2answers
39 views

Logic - What does ∴ mean in a truth table?

I see the symbol used, and I've never seen it logically defined. In words, It's defined as a symbol meaning 'therefore'. Because of a lack of definition, I have no idea why this is false: ...
1
vote
0answers
39 views

Is this deduction false?

Is this deduction accurate? I have been trying to find out how we can get ~~B by showing contradiction by asssuming A.
0
votes
1answer
20 views

Rule of inference proof

"Either I go to library or if I wait for my mom then I have to go to the party." "I will go to the party if I meet my friends" "If I go to the library then I will finish my homework." "I did not ...
1
vote
2answers
942 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
0
votes
0answers
10 views

DNF using laws on 3 literals and simplifying

Can someone tell me how to turn this into disjunctive normal form please? For Q1, I find it easy to remove implications, double negations and use distributive law. However I am having a hard time ...
0
votes
1answer
45 views
0
votes
1answer
1k 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 ...
2
votes
2answers
32 views

Compactness theorem, propositional calculus

Please help me with this problem. Prove that if $\land \Phi \models \lor \Psi$ (both $\Phi$ and $\Psi$ infinite) then there exist $\phi_1,...,\phi_n$ from $\Phi$ and $\psi_1,...,\psi_m$ from $\Psi$ ...