how the fuck do you prove this without truth tables? algebraically

Its a definition. It doesn't require a proof.

File: umm.jpg (20KB, 530x106px) Image search: [Google]

20KB, 530x106px

>>8918260
my prof said to prove it algebraically though.as an exercise.

>>8918261
Truth table method is the only way I can think of proving this.

>>8918260

The definition might be p->q & q->p

so
p<->q
p->q & q->p //by definition
(~p or q) & (~q or p) //by definition
~p&~q or q&~q or ~p&p or q&p //expanding
~p&~q or q&p //killing impossible x and not x

QED

>>8918261
~(p<->q)
~(p->q & q->p)
~(p->q) or ~(q->p)
~(~p or q) or ~(~q or p)
(p & ~q) or (q & ~p)
(p <-> ~q) //by ex16

>>8918266
>t. brainlet cs major

>>8918292
truth table method is the most appropriate proof here.

>>8918293
>brute force
>appropriate
>ever

No.

>>8918289
You have a mistake

>>8918295
>t. engineer who took "Intro to Logic For Engineers"

>>8918296
No I don't, q == ~~q

>>8918295
Truth table method is actually faster than any of the proofs listed here, even if you count by character length.

>>8918289
>>8918287
Informal proofs

>>8918287
informal
>>8918289
informal and wrong

>>8918305
It's a 100% rigorous proof acceptable in any mathematical logic course. Only high schoolers do proofs by pattern matching axioms.

>>8918301
Truth tables blow up exponentially and have 0 insight to them. You should never look at them beyond day 1 freshman year.

>>8918320
>t. state school engineer

>>8918296
>>8918316
>>8918305
>samefagging butthurt CS major

>>8918325
go to bed

>>8918287
>>8918289
op here. i can't believe i missed that definition of the biconditional. i thought i could only use conjuctive and disjunctive clauses.

File: 1455310679806.png (287KB, 836x1065px) Image search: [Google]

287KB, 836x1065px

>>8918328

The >>>/g/hetto is that way, go home brainlet.

File: Untitled.jpg (119KB, 550x596px) Image search: [Google]

119KB, 550x596px

here are the other ones in case you were interested. im gonna try them out using that [(p=>q ^ (q=>p)] format of the definition rather than the conjunction.

>>8918332
What kind of autism do you have that you think calling someone a CS major is an insult?

I'm a statistics grad student fyi

>>8918335
>grad student
>can't into basic logic

Sure you are, sure.

>>8918341
where am i wrong

>>8918342
You're the one claiming >>8918289 is wrong and are spamming the thread multiple times at that.

>>8918353
And its not a proper proof. Where am I wrong?

>>8918256
P IFF Q === P IMPLIES Q AND Q IMPLIES P
P IMPLIES Q AND Q IMPLIES P ===
(NOT P OR Q) AND (NOT Q OR P)

>>8918355
It's a 100 percent rigorous proof. You're not articulating any counter argument.

>>8918332
>Thinking physics is mathematical
>Thinking DEs are complicated
>Rock me kekadeus

>>8918362
I never said it wasn't rigorous.
Its informal. There is a difference, but I guess only "CS brainlets" know this.

>>8918334
OP here there is no way to simplify 18 if it's just a conditional is there? maybe (p v -q) but how would that lead back to the implication?

>>8918375
still wrong.

How do you know how many IPs are in this thread?

>>8918366
You said twice that it was wrong: >>8918296 and >>8918316

Protip: you can't hide behind anonymity if there are only 3 IPs in the thread (op, you, and I)

>hurr durr, you're not using 2 column proofs like philosophy 101 students do so it must be wrong.

~(p<->q)
~(p->q & q->p) // definition
~(p->q) or ~(q->p) //De Morgan
~(~p or q) or ~(~q or p) //definition
(p & ~q) or (q & ~p) // De Morgan
(p <-> ~q) //by ex16

See, not wrong anywhere.

>informal

No one uses "formal" proofs like it's defined in mathematical logic to actually prove stuff. It's only used to prove theorems on metamathematics and with ATP.

>>8918363
>so called graduate student in stats
>thinks calc 2's DEs is the highest math in physics

Stop lying on the internet. Data ""science"" isn't a statistics degree.

File: Capture.png (11KB, 1331x146px) Image search: [Google]

11KB, 1331x146px

>>8918383
>being this new

>>8918385
>still wrong

Just deal with yourself

>>8918378
All of these kinds of problems are solved by unpacking the definitions and meeting in the middle

(p->q) = ~p or q
(~q->~p) = ~~q or ~p = q or ~p = ~p or q

QED

>>8918385
>>8918384
>>8918362
>>8918353
>>8918341
>>8918332
>>8918325
>>8918320
>>8918300
>>8918295
>>8918292
>>8918289
>>8918287

Why is this man's penis so small?

File: 1201386589289.png (288KB, 497x363px) Image search: [Google]

288KB, 497x363px

>>8918387
>>8918383
>not an argument

>>8918390
>Ad hominem

>>8918385
>>8918384
>>8918362
>>8918353
>>8918341
>>8918332
>>8918325
>>8918320
>>8918300
>>8918295
>>8918292
>>8918287
>>8918261

let me guess... CS Major?

File: 1383411540423.png (31KB, 625x625px) Image search: [Google]

31KB, 625x625px

>>8918394

File: 1478673937250.gif (494KB, 387x305px) Image search: [Google]

494KB, 387x305px

>>8918385
>>8918384
>>8918362
>>8918353
>>8918341
>>8918332
>>8918325
>>8918320
>>8918300
>>8918295
>>8918292
>>8918289
>>8918287

is it just me or is this guys wiener oddly small

File: willsmit.gif (500KB, 500x399px) Image search: [Google]

500KB, 500x399px

>>8918287
>>8918289

File: 11177744.jpg (86KB, 400x260px) Image search: [Google]

86KB, 400x260px

>>8918300
>>8918292
>>8918289
>>8918287

File: (You).webm (376KB, 473x400px) Image search: [Google]

376KB, 473x400px

>>8918401
>>8918400
>>8918398
>>8918390
>all those (you)'s

File: small_penis_engineer.jpg (9KB, 232x217px) Image search: [Google]

9KB, 232x217px

>>8918402

>>8918389
so i can't go from one to the other? damn this doesn't seem hard but for some reason i keep fudging up the steps when i see no equivalence blatantly in my face when unpacking from the implication to the negation.

>>8918256

1(p&q)v(~p&~q)
2||p
case 1
3|||p&q velim1
4|||q &elim3
case 2
5|||~p&~q velim1
6||| ~p &elim5
7|||q cont intro 2,6
8|| p->q ->intro 2,7
9|| q
case 1
10|||p&q velim1
11|||p &elim10
case 2
12|||~p&~q velim1
13||| ~q &elim12
14|||p cont intro 9,13
15||q->p ->intro 9,14
16|p<->q <->intro 9,15

i think this is sort of what you want it to look like but the other way around
just being like "HUR DUR THIS IS A DEFINITION" probably isn't the right answer
but what the fuck do i know im an engineer so im gonna go suck some robot dicks
also i havent done this shit in forever so i probably forgot the correct use of velim or &elim since i made them do the same thing even though i was just trying to prove by cases

>>8918409
last line should be
16|p<->q <->intro 8,15

>>8918408
>so i can't go from one to the other

No, you can. I'm just saying it's easier to meet in the middle rather than try to figure out how to repack it directly.

>Question
Show statement A == statement Z

>Scrap Paper
A == B == C ... == R == S
Z == Y == X ... == T == S

>Actual proof
A == B == C ... == R == S == T ... == X == Y == Z

>>8918426
ok i think i get what you mean. i just did exercises 20 and got this.

prove: -(p xor q) = (p<=>q)

p xor q = (p v q) ^ (-p ^ -q)

p <=> q = (p=>q) ^ (q=>p)
=(-p v q) ^ (-q v p)

- ( p xor q) = - [(p v q) ^ (-p v -q)]
=[(-p ^ -q) v (p ^ q)]
=p<=>q

QED? i did De Morgan's Law on the -p v -q...

is it proper form to write a proof as two things being equal to the same thing, therefore they're equal to each other?

>>8918446
Euclid's first axiom:

Things which are equal to the same thing are equal to each other.

>>8918451
is there a proof for this?

if i have

(-p^q) v (-p^r) v (-q^r) v (r)

can i eliminate (-p^r) v (-q^r) to just have (-p^q) v (r)? this is for 23 from >>8918334

>>8918256
Replace the equals sign and prove the tautology

>>8918287
>>8918289
Correct proofs, thanks for posting

>>8918287
>>8918289
>>8918999
samefag

kys

>>8918256
[math] p \iff q \\
(p \implies q) \land (q \implies p) \text{ Definition of equivalence} \\
( \neg p \lor q) \land ( \neg q \lor p) \text{ Definition of implication} \\
(( \neg p \lor q) \land \neg q) \lor (( \neg p \lor q) \land p) \text{ Distribution } \\
((\neg q \land q) \lor (\neg q \land \neg p)) \lor ((p \land \neg p) \lor (p \land q)) \text{ Distribution} \\
( \neg q \land \neg p) \lor (p \land q) \text{ Removal of contradictions} \\
(p \land q) \lor ( \neg p \land \neg q) \text{ Commutativity } [/math]

God fucking damn. I did propositional logic as a freshman and I was never ever ever asked to prove this. Holy fuck your professor is savage but it can be done.

Note that I haven't really studied more propositional logic after that so if I could do it you should be able to do it.

>>8918668

Yes, just factor out
(-p&r) or (-q&r) or (r) = (-p or -q or 1)&r = 1&r = r

File: Same.png (5KB, 355x150px) Image search: [Google]

5KB, 355x150px

>>8919099
>being unable to tell who's who

>>8918256
>>8918261
>>8918331
>>8918334
>>8918378
>>8918408
>>8918430
>>8918446
>>8918631
>>8918668
ip 1 (OP)
>>8918260
>>8918266
>>8918293
>>8918296
>>8918299
>>8918301
>>8918305
>>8918316
>>8918323
>>8918328
>>8918335
>>8918342
>>8918355
>>8918363
>>8918366
>>8918383
>>8918387
>>8918390
>>8918394
>>8918398
>>8918400
>>8918401
>>8918403
>>8918405
ip 2 (faggot)
>>8918287
>>8918289
>>8918292
>>8918300
>>8918320
>>8918325
>>8918332
>>8918341
>>8918353
>>8918362
>>8918384
>>8918385
>>8918389
>>8918392
>>8918397
>>8918402
>>8918426
>>8919287
>>8919325
ip 3 (me)
>>8918360
ip 4
>>8918409
>>8918416
ip 5
>>8918425
ip 6
>>8918693
ip 7
>>8918999
ip 8
>>8919099
ip 9
>>8919130
ip 10

>>8919287
how does that work???

>>8918256
Did u try distributing?

>>8919755
Boolean algebra. Let * be AND and + be OR with AND being higher in precedence.

A*(B+C)=A*B+A*C //Distributivity
A+(B*C)=(A+B)*(A+C) //looks weird but follows from DeMorgan'ing the 1st one
A+1 = 1
A+0 = A
A*1 = A
A*0 = 0

>>8919898
but how can you ignore the p and q?

>>8919326
Nice photoshop on the picture bro. Underline @ the last 9 was cut way too early. But nice try bro

>>8919935
-p or -q or true
-p or (-q or true)
-p or (true)
true

>>8920116
you get a T from factoring out r though? what definition lets you do that?

>>8920132
r = true & r

You want to prove a semantic equivalency, which means you must show a semantic arrow going both ways. The left side's equivalency is not semantic btw, it's syntactic.

>>8918256
Are you in my summer class? A school in NC?

File: 352.jpg (24KB, 396x385px) Image search: [Google]

24KB, 396x385px

>>8918256
>>8918261
[math]p\leftrightarrow q = p\rightarrow q \wedge p\leftarrow q [/math]
[math]\qquad \quad = (\neg p \vee q)\wedge(p\vee\neg q) [/math]
[math]\qquad \quad = (p \wedge \neg p) \vee (\neg p \wedge \neg q) \vee (p \wedge q) \vee (\neg q \wedge q)[/math]
[math]\qquad \quad = (p \wedge q) \vee (\neg p \wedge \neg q)[/math]

>>8921256
You're half done since you've only shown [math]\Leftarrow[/math]

Next you must show [math]\Rightarrow[/math]

>>8918256
First we seek to show the forward direction

[math]1 (1) p \iff q, \ \text{Assumption}[/math]
[math]1 (2) (p \Rightarrow q) \land (q \Rightarrow p), \ \text{Definition of the biconditional} [/math]
[math]1 (3) p \Rightarrow q, \ 2 \ \text{Conjunction elimination} [/math]
[math]1 (4) q \Rightarrow p, \ 2 \ \text{Conjunction elimination}[/math]
[math](5) p \lor \lnot p , \ \text{Theorem Introduction: Law of excluded middle} [/math]
[math]6 (6) p, \ \text{Assumption} [/math]
[math]1, 6 (7)q, \ 6,3 \ \text{Modus ponens} [/math]
[math]1, 6 (8) p \land q, \ 6,7 \ \text{Conjunction introduction} [/math]
[math]1, 6 (9) (p \land q) \lor (\lnot p \land \lnot q) , \ 8 \ \text{Disjunction introduction} [/math]
[math]10 (10) \lnot p, \ \text{Assumption} [/math]
[math]1, 10 (11) \lnot q, \ 4,10 \ \text{Modus tolens}[/math]
[math]1, 10 (12) \lnot p \land \lnot q, \ 10,11 \ \text{Conjunction introduction} [/math]
[math]1, 10 (13) (p \land q) \lor (\lnot p \land \lnot q), \ 12 \ \text{Disjunction introduction} [/math]
[math]1 (14) (p \land q) \lor (\lnot p \land \lnot q), \ 5, 6, 9, 10, 13, \ \text{Disjunction elimination} [/math]

The other direction is an exercise

>>8921275
equality is symmetric

>>8921326
You have to prove both sides retard

>>8921338
Can't you read from right to left, brainlet?

>>8918261
Oh, Rosen's discrete maths, we meet again.